시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 707 146 107 21.022%

문제

무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫 줄에는 세 정수 n, m, k가 주어진다. n은 그래프의 정점의 개수 (2 ≤ n ≤ 1,000)이고, m은 간선의 개수, k는 문제에 설명되어 있는 파란색 간선의 개수 (0 ≤ k < n) 이다.

다음 m개 줄에는 간선의 정보가 주어지며, 각 정보는 세 정수 c, f, t로 이루어져 있다. c는 간선의 색상을 나타내며, 빨간색인 경우에는 R, 파란색인 경우에는 B이다. f와 t는 정수로 간선이 연결하는 두 정점을 나타낸다. (1 ≤ f,t ≤ n, t ≠ t) 두 정점을 연결하는 간선은 최대 한 개이다.

입력의 마지막 줄에는 0이 세 개 주어진다.

출력

각 테스트 케이스마다 파란색 간선이 정확하게 k개인 스패닝 트리를 만들 수 있으면 1, 없으면 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
W3sicHJvYmxlbV9pZCI6IjQ3OTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4MDhcdWI0ZGMgXHViZTE0XHViOGU4IFx1YzJhNFx1ZDMyOFx1YjJkZCBcdWQyYjhcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmIzNFx1YmMyOVx1ZDVhNSwgXHViYjM0XHVhYzAwXHVjOTExXHVjZTU4LCBcdWM1ZjBcdWFjYjAgXHVhZGY4XHViNzk4XHVkNTA0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YWMwMSBcdWFjMDRcdWMxMjBcdWM3NDAgXHViZTY4XHVhYzA0XHVjMGM5IFx1YjYxMFx1YjI5NCBcdWQzMGNcdWI3ODBcdWMwYzlcdWM3M2NcdWI4NWMgXHVjMGM5XHVjZTYwXHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWMyYTRcdWQzMjhcdWIyZGQgXHVkMmI4XHViOWFjIFx1YzkxMSBcdWQzMGNcdWI3ODBcdWMwYzkgXHVhYzA0XHVjMTIwXHVjNzc0IFx1YzgxNVx1ZDY1NVx1ZDc4OCBrXHVhYzFjXHVjNzc4IFx1YWM4M1x1Yzc3NCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNWM2XHViMjk0XHVjOWMwIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEzOCBcdWM4MTVcdWMyMTggbiwgbSwga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIG5cdWM3NDAgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggKDIgJmxlOyBuICZsZTsgMSwwMDApXHVjNzc0XHVhY2UwLCBtXHVjNzQwIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMTgsIGtcdWIyOTQgXHViYjM4XHVjODFjXHVjNWQwIFx1YzEyNFx1YmE4NVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVkMzBjXHViNzgwXHVjMGM5IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMTggKDAgJmxlOyBrICZsdDsgbikgXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWMwMSBcdWM4MTVcdWJjZjRcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCBjLCBmLCB0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIGNcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzBjOVx1YzBjMVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsIFx1YmU2OFx1YWMwNFx1YzBjOVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgUiwgXHVkMzBjXHViNzgwXHVjMGM5XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBCXHVjNzc0XHViMmU0LiBmXHVjNjQwIHRcdWIyOTQgXHVjODE1XHVjMjE4XHViODVjIFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzgxMFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuICgxICZsZTsgZix0ICZsZTsgbiwgdCAmbmU7IHQpIFx1YjQ1MCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc0MCBcdWNkNWNcdWIzMDAgXHVkNTVjIFx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWMxMzggXHVhYzFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQzMGNcdWI3ODBcdWMwYzkgXHVhYzA0XHVjMTIwXHVjNzc0IFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBrXHVhYzFjXHVjNzc4IFx1YzJhNFx1ZDMyOFx1YjJkZCBcdWQyYjhcdWI5YWNcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzQgMSwgXHVjNWM2XHVjNzNjXHViYTc0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ3OTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSZWRcL0JsdWUgU3Bhbm5pbmcgVHJlZSIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYW4gdW5kaXJlY3RlZCwgdW53ZWlnaHRlZCwgY29ubmVjdGVkIGdyYXBoLCB3aGVyZSBlYWNoIGVkZ2UgaXMgY29sb3JlZCBlaXRoZXIgYmx1ZSBvciByZWQsIGRldGVybWluZSB3aGV0aGVyIGEgc3Bhbm5pbmcgdHJlZSB3aXRoIGV4YWN0bHkgayBibHVlIGVkZ2VzIGV4aXN0cy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIHdpbGwgYmUgc2V2ZXJhbCB0ZXN0IGNhc2VzIGluIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBiZWdpbiB3aXRoIGEgbGluZSB3aXRoIHRocmVlIGludGVnZXJzOiZuYnNwOzxcL3A+XHJcblxyXG48cHJlPlxyXG5uIG0gazxcL3ByZT5cclxuXHJcbjxwPldoZXJlIG4gKDImbGU7biZsZTsxLDAwMCkgaXMgdGhlIG51bWJlciBvZiBub2RlcyBpbiB0aGUgZ3JhcGgsIG0gKGxpbWl0ZWQgYnkgdGhlIHN0cnVjdHVyZSBvZiB0aGUgZ3JhcGgpIGlzIHRoZSBudW1iZXIgb2YgZWRnZXMgaW4gdGhlIGdyYXBoLCBhbmQgayAoMCZsZTtrJmx0O24pIGlzIHRoZSBudW1iZXIgb2YgYmx1ZSBlZGdlcyBkZXNpcmVkIGluIHRoZSBzcGFubmluZyB0cmVlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IG0gbGluZXMgd2lsbCBjb250YWluIHRocmVlIGVsZW1lbnRzLCBkZXNjcmliaW5nIHRoZSBlZGdlczombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuYyBmIHQ8XC9wcmU+XHJcblxyXG48cD5XaGVyZSBjIGlzIGEgY2hhcmFjdGVyLCBlaXRoZXIgY2FwaXRhbCAmbHNxdW87UiZyc3F1bzsgb3IgY2FwaXRhbCAmbHNxdW87QiZyc3F1bzssIGluZGljYXRpbmcgdGhlIGNvbG9yIG9mIHRoZSBlZGdlLCBhbmQgZiBhbmQgdCBhcmUgaW50ZWdlcnMgKDEmbGU7Zix0JmxlO24sIHQmbmU7ZikgaW5kaWNhdGluZyB0aGUgbm9kZXMgdGhhdCBlZGdlIGdvZXMgZnJvbSBhbmQgdG8uIFRoZSBncmFwaCBpcyBndWFyYW50ZWVkIHRvIGJlIGNvbm5lY3RlZCwgYW5kIHRoZXJlIGlzIGd1YXJhbnRlZWQgdG8gYmUgYXQgbW9zdCBvbmUgZWRnZSBiZXR3ZWVuIGFueSBwYWlyIG9mIG5vZGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgaW5wdXQgd2lsbCBlbmQgd2l0aCBhIGxpbmUgd2l0aCB0aHJlZSAwcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBzaW5nbGUgbGluZSwgY29udGFpbmluZyAxIGlmIGl0IGlzIHBvc3NpYmxlIHRvIGJ1aWxkIGEgc3Bhbm5pbmcgdHJlZSB3aXRoIGV4YWN0bHkgayBibHVlIGVkZ2VzLCBhbmQgMCBpZiBpdCBpcyBub3QgcG9zc2libGUuIE91dHB1dCBubyBleHRyYSBzcGFjZXMsIGFuZCBkbyBub3Qgc2VwYXJhdGUgYW5zd2VycyB3aXRoIGJsYW5rIGxpbmVzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==