Red-Blue Spanning Tree

You are given an undirected, unweighted, connected graph. Each edge is colored either red (R) or blue (B). Write a program that determines whether the graph has a spanning tree containing exactly $k$ blue edges.

The input consists of several test cases.

The first line of each test case contains three integers $n$, $m$, and $k$. Here $n$ is the number of vertices ($2 \le n \le 1{,}000$), $m$ is the number of edges, and $k$ is the required number of blue edges in the spanning tree ($0 \le k < n$).

Each of the next $m$ lines describes one edge with three values $c$, $f$, and $t$. The color $c$ is R for a red edge or B for a blue edge. $f$ and $t$ are the two vertices joined by the edge ($1 \le f, t \le n$, $f \ne t$). At most one edge connects any pair of vertices.

The last line of the input is 0 0 0, which must not be processed.

For each test case, print 1 on its own line if a spanning tree with exactly $k$ blue edges can be formed, or 0 otherwise.