NYU Summer Practice 13

Start

2017-08-12 19:00 CEST

NYU Summer Practice 13

End

2017-08-15 00:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -432 days 23:33:06

Time elapsed

53:00:00

Time remaining

0:00:00

Problem G
Red/Blue Spanning Tree

Given an undirected, unweighted, connected graph, where each edge is colored either blue or red, determine whether a spanning tree with exactly $k$ blue edges exists.

Input

There will be a single test case in the input. Each test case will begin with a line with three integers:

$n \ m \ k$

Where $n$ ($2 \le n \le 1\, 000$) is the number of nodes in the graph, $m$ (limited by the structure of the graph) is the number of edges in the graph, and $k$ ($0 \le k < n$) is the number of blue edges desired in the spanning tree. Each of the next $m$ lines will contain three elements, describing the edges:

$c \ f \ t$

Where $c$ is a character, either capital R or capital B, indicating the color of the edge, and $f$ and $t$ are integers ($1 \le f, t \le n, t \ne f$) indicating the nodes that edge goes from and to. The graph is guaranteed to be connected, and there is guaranteed to be at most one edge between any pair of nodes.

Output

Output a single line, containing $1$ if it is possible to build a spanning tree with exactly $k$ blue edges, and $0$ if it is not possible.

Sample Input 1 Sample Output 1
3 3 2
B 1 2
B 2 3
R 3 1
1
Sample Input 2 Sample Output 2
2 1 1
R 1 2
0