Красное/Синее Остовное Дерево
Дан неориентированный, невзвешенный, связный граф, в котором каждое ребро окрашено либо в синий, либо в красный цвет. Определите, можно ли построить остовное дерево, содержащее ровно 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), обозначающие узлы, между которыми проходит ребро. Граф гарантированно связный, и гарантируется, что между любой парой узлов может быть не более одного ребра.
Входные данные заканчиваются строкой с тремя нулями.
Выходные данные
Для каждого теста выведите одну строку, содержащую 1, если возможно построить остовное дерево с ровно k синими рёбрами, и 0, если это невозможно. Не выводите лишние пробелы и не разделяйте ответы пустыми строками.