Задан неориентированный, невзвешенный, связный граф, каждое ребро которого окрашено в синий или красный цвет. Определите, существует ли для заданного графа остовное дерево, с точно \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}, если это не предоставляется возможным. Выводить следует без лишних пробелов и не отделяя ответы пустыми строками.