시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 735 152 117 23.494%

문제

무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 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, f ≠ 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+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWMwMSBcdWM4MTVcdWJjZjRcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCBjLCBmLCB0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIGNcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzBjOVx1YzBjMVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsIFx1YmU2OFx1YWMwNFx1YzBjOVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgUiwgXHVkMzBjXHViNzgwXHVjMGM5XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBCXHVjNzc0XHViMmU0LiBmXHVjNjQwIHRcdWIyOTQgXHVjODE1XHVjMjE4XHViODVjIFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzgxMFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuICgxICZsZTsgZiwgdCAmbGU7IG4sIGYgJm5lOyB0KSBcdWI0NTAgXHVjODE1XHVjODEwXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NDAgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVjMTM4IFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVkMzBjXHViNzgwXHVjMGM5IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM4MTVcdWQ2NTVcdWQ1NThcdWFjOGMga1x1YWMxY1x1Yzc3OCBcdWMyYTRcdWQzMjhcdWIyZGQgXHVkMmI4XHViOWFjXHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTc0IDEsIFx1YzVjNlx1YzczY1x1YmE3NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0NzkyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUmVkXC9CbHVlIFNwYW5uaW5nIFRyZWUiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGFuIHVuZGlyZWN0ZWQsIHVud2VpZ2h0ZWQsIGNvbm5lY3RlZCBncmFwaCwgd2hlcmUgZWFjaCBlZGdlIGlzIGNvbG9yZWQgZWl0aGVyIGJsdWUgb3IgcmVkLCBkZXRlcm1pbmUgd2hldGhlciBhIHNwYW5uaW5nIHRyZWUgd2l0aCBleGFjdGx5IGsgYmx1ZSBlZGdlcyBleGlzdHMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSB3aWxsIGJlIHNldmVyYWwgdGVzdCBjYXNlcyBpbiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHdpbGwgYmVnaW4gd2l0aCBhIGxpbmUgd2l0aCB0aHJlZSBpbnRlZ2VyczombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxubiBtIGs8XC9wcmU+XHJcblxyXG48cD5XaGVyZSBuICgyJmxlO24mbGU7MSwwMDApIGlzIHRoZSBudW1iZXIgb2Ygbm9kZXMgaW4gdGhlIGdyYXBoLCBtIChsaW1pdGVkIGJ5IHRoZSBzdHJ1Y3R1cmUgb2YgdGhlIGdyYXBoKSBpcyB0aGUgbnVtYmVyIG9mIGVkZ2VzIGluIHRoZSBncmFwaCwgYW5kIGsgKDAmbGU7ayZsdDtuKSBpcyB0aGUgbnVtYmVyIG9mIGJsdWUgZWRnZXMgZGVzaXJlZCBpbiB0aGUgc3Bhbm5pbmcgdHJlZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBtIGxpbmVzIHdpbGwgY29udGFpbiB0aHJlZSBlbGVtZW50cywgZGVzY3JpYmluZyB0aGUgZWRnZXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbmMgZiB0PFwvcHJlPlxyXG5cclxuPHA+V2hlcmUgYyBpcyBhIGNoYXJhY3RlciwgZWl0aGVyIGNhcGl0YWwgJmxzcXVvO1ImcnNxdW87IG9yIGNhcGl0YWwgJmxzcXVvO0ImcnNxdW87LCBpbmRpY2F0aW5nIHRoZSBjb2xvciBvZiB0aGUgZWRnZSwgYW5kIGYgYW5kIHQgYXJlIGludGVnZXJzICgxJmxlO2YsdCZsZTtuLCB0Jm5lO2YpIGluZGljYXRpbmcgdGhlIG5vZGVzIHRoYXQgZWRnZSBnb2VzIGZyb20gYW5kIHRvLiBUaGUgZ3JhcGggaXMgZ3VhcmFudGVlZCB0byBiZSBjb25uZWN0ZWQsIGFuZCB0aGVyZSBpcyBndWFyYW50ZWVkIHRvIGJlIGF0IG1vc3Qgb25lIGVkZ2UgYmV0d2VlbiBhbnkgcGFpciBvZiBub2Rlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IHdpbGwgZW5kIHdpdGggYSBsaW5lIHdpdGggdGhyZWUgMHMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgc2luZ2xlIGxpbmUsIGNvbnRhaW5pbmcgMSBpZiBpdCBpcyBwb3NzaWJsZSB0byBidWlsZCBhIHNwYW5uaW5nIHRyZWUgd2l0aCBleGFjdGx5IGsgYmx1ZSBlZGdlcywgYW5kIDAgaWYgaXQgaXMgbm90IHBvc3NpYmxlLiBPdXRwdXQgbm8gZXh0cmEgc3BhY2VzLCBhbmQgZG8gbm90IHNlcGFyYXRlIGFuc3dlcnMgd2l0aCBibGFuayBsaW5lcy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=