Exploring the Tree in an RTS Game

Small M is playing a real-time strategy game on a tree-shaped map. The map is represented by a tree with (n) nodes and (n-1) edges. The nodes are numbered from (1) to (n). Initially, only node (1) is known.

During the game, you can perform an exploration operation by calling the function (explore(x,y)) with two nodes (x) and (y) ((x \neq y)), where (x) must be a known node and (y) can be any node. The function returns the second node on the unique shortest path from (x) to (y) (i.e. the neighbor of (x) on that path). If this returned node is not yet known, it becomes known.

Your task is to implement the function (play(n, T, dataType)) so that using at most (T) exploration operations, all nodes become known. The interactor will call (play) exactly once at the beginning of each test case.

Hint: Since the tree is connected and there is a unique simple path between any two nodes, a breadth-first search strategy starting from node (1) can help you discover all nodes with an appropriate sequence of (explore) operations.

inputFormat

The input consists of multiple lines.

The first line contains three integers (n), (T) and (dataType) where (n) is the number of nodes in the tree, (T) is the maximum number of exploration operations allowed, and (dataType) indicates the test data type.

Each of the next (n-1) lines contains two integers (u) and (v), which indicate that there is an undirected edge between nodes (u) and (v).

outputFormat

This is an interactive problem. However, in our offline simulation, the program outputs the sequence of exploration operations it chooses.

The output begins with an integer representing the number of (explore) calls performed. Each subsequent line contains two integers (x) and (y), corresponding to a call to (explore(x,y)). The judge will verify that, after these operations, all nodes become known.

sample

4 3 1
1 2
2 3
2 4

3
1 2
2 3
2 4