Məsələlər
Красно-синее остовное дерево
Красно-синее остовное дерево
Задан неориентированный, невзвешенный, связный граф, каждое ребро которого окрашено в синий или красный цвет. Определите, существует ли для заданного графа остовное дерево, с точно \textbf{k} синими рёбрами.
\InputFile
Входные данные могут содержать несколько тестовых наборов. Каждый тест будет начинаться со строки с тремя целыми числами:
\textbf{n m k}
где \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{1000}) - количество вершин в графе, \textbf{m} (ограничено структурой графа) - количество рёбер в графе, и \textbf{k} (\textbf{0} ≤ \textbf{k} < \textbf{n}) -- количество синих рёбер в желаемом дереве.
Каждая из последующих \textbf{m} строк будет состоять из трех элементов, описывающих ребра:
\textbf{c f t}
где \textbf{c} - символ, прописная латинская буква '\textbf{R}' или '\textbf{B}', указывающая цвет ребра, и целые числа \textbf{f} и \textbf{t} (\textbf{1} ≤ \textbf{f}, \textbf{t} ≤ \textbf{n}, \textbf{t} ≠ \textbf{f}) -- указывающие вершины, которые соединяет соответствующее ребро. Граф гарантированно будет связным, и в нём гарантированно будет не более одного ребра между любыми двумя вершинами. Входные данные завершаются строкой, содержащей три \textbf{0}.
\OutputFile
Для каждого теста выведите одну строку, содержащую \textbf{1}, если можно построить остовное дерево с точно \textbf{k} синими рёбрами, и \textbf{0}, если это не предоставляется возможным. Выводить следует без лишних пробелов и не отделяя ответы пустыми строками.
Giriş verilənləri #1
3 3 2 B 1 2 B 2 3 R 3 1 2 1 1 R 1 2 0 0 0
Çıxış verilənləri #1
1 0