레드 블루 스패닝 트리

무방향 · 무가중치 연결 그래프가 주어진다. 각 간선은 빨간색(R) 또는 파란색(B)으로 칠해져 있다. 이 그래프의 스패닝 트리 중에서 파란색 간선이 정확히 $k$개인 것이 존재하는지 판별하는 프로그램을 작성하시오.

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

각 테스트 케이스의 첫 줄에는 세 정수 $n$, $m$, $k$가 주어진다. $n$은 그래프의 정점 수($2 \le n \le 1{,}000$), $m$은 간선 수, $k$는 스패닝 트리에 포함되어야 하는 파란색 간선의 수($0 \le k < n$)이다.

이어지는 $m$개의 줄에는 각 간선의 정보가 세 값 $c$, $f$, $t$로 주어진다. $c$는 간선의 색으로, 빨간색이면 R, 파란색이면 B이다. $f$와 $t$는 간선이 잇는 두 정점의 번호이다($1 \le f, t \le n$, $f \ne t$). 두 정점을 잇는 간선은 최대 한 개이다.

입력의 마지막 줄에는 0 0 0이 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 파란색 간선이 정확히 $k$개인 스패닝 트리를 만들 수 있으면 1을, 만들 수 없으면 0을 한 줄에 출력한다.