Задано неорієнтовний, незважений, зв'язний граф, кожне ребро якого зафарбовано у синій або червоний колір. Визначте, чи існує для заданого графа остовне дерево, з точно \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}, якщо подібне не можливо. Виводити потрібно без зайвих пропусків і не відокремлюючи відповіді порожніми рядками.