eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Червоно-синє остовне дерево

Червоно-синє остовне дерево

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

Задано неорієнтовний, незважений, зв'язний граф, кожне ребро якого зафарбовано у синій або червоний колір. Визначте, чи існує для заданого графа остовне дерево, з точно k синіми ребрами.

Вхідні дані

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

n m k

де n (2n1000) - кількість вершин у графі, m (обмежено структурою графа) - кількість ребер у графі, і k (0k < n) – кількість синіх ребер у бажаному дереві.

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

c f t

де c - символ, прописна латинська літера 'R' або 'B', яка вказує колір ребра, і цілі числа f і t (1f, tn, tf) – які вказують вершини, які з'єднують відповідне ребро. Граф гарантовано буде зв'язним, і у ньому гарантовано буде не більше одного ребра між довільними двома вершинами. Вхідні дані завершуються рядком, який містить три 0.

Вихідні дані

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

Приклад

Вхідні дані #1
3 3 2
B 1 2
B 2 3
R 3 1
2 1 1
R 1 2
0 0 0
Вихідні дані #1
1
0