Червоний/Синій Остовний Дерево
Дано неорієнтований, неваговий, зв'язний граф, у якому кожне ребро пофарбоване або в синій, або в червоний колір. Потрібно визначити, чи існує остове дерево з рівно 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, якщо це неможливо. Не виводьте зайвих пробілів і не розділяйте відповіді порожніми рядками.