Red Blue Spanning Tree 2

Interview

Time limit1sMemory limit128 MB

Summary

Given a connected undirected graph whose edges are red or blue, decide whether some spanning tree uses exactly k blue edges, and print one if it does.

Level: Medium7 of 10
Topics: Graph, Minimum spanning tree, Greedy, Union-find
Solved: No attempts yet

Problem

You are given an undirected, unweighted, connected graph. Each edge of the graph is colored red or blue. Write a program that determines whether the graph has a spanning tree with exactly k blue edges, and if so, outputs any one of them.

Input

The first line gives three integers n, m, k. n is the number of vertices (2 ≤ n ≤ 1,000), m is the number of edges, and k is the number of blue edges described in the problem (0 ≤ k < n).

The next m lines give the edges. Each line has three integers c, f, t. c is the color of the edge: R for red, B for blue. f and t are the two vertices the edge connects (1 ≤ f, t ≤ n, f ≠ t). There is at most one edge between any two vertices.

Output

If a spanning tree with exactly k blue edges exists, output n-1 lines. On each line, print the two endpoints of one edge.

If no spanning tree satisfies the condition, output 0.

Examples2

Example 1
Input
```
3 3 2
B 1 2
B 2 3
R 3 1
```
Expected output
```
1 2
2 3
```
Example 2
Input
```
2 1 1
R 1 2
```
Expected output
```
0
```