Красно-синее остовное дерево

Задан неориентированный, невзвешенный, связный граф, каждое ребро которого окрашено в синий или красный цвет. Определите, существует ли для заданного графа остовное дерево, с точно k синими рёбрами.

Входные данные

Входные данные могут содержать несколько тестовых наборов. Каждый тест будет начинаться со строки с тремя целыми числами:

n m k

где n (2 ≤ n ≤ 1000) - количество вершин в графе, m (ограничено структурой графа) - количество рёбер в графе, и k (0 ≤ k < n) – количество синих рёбер в желаемом дереве.

Каждая из последующих m строк будет состоять из трех элементов, описывающих ребра:

c f t

где c - символ, прописная латинская буква 'R' или 'B', указывающая цвет ребра, и целые числа f и t (1 ≤ f, t ≤ n, t ≠ f) – указывающие вершины, которые соединяет соответствующее ребро. Граф гарантированно будет связным, и в нём гарантированно будет не более одного ребра между любыми двумя вершинами. Входные данные завершаются строкой, содержащей три 0.

Выходные данные

Для каждого теста выведите одну строку, содержащую 1, если можно построить остовное дерево с точно k синими рёбрами, и 0, если это не предоставляется возможным. Выводить следует без лишних пробелов и не отделяя ответы пустыми строками.