Mapping Silvermill City

This is an interactive problem.

Silvermill City consists of \(N\) intersections and \(N-1\) bidirectional roads numbered from \(0\) to \(N-2\). The \(i\)-th road connects intersections \(A_i\) and \(B_i\) and requires \(W_i\) minutes to travel, regardless of the direction. It is guaranteed that any two intersections can reach each other via these roads.

In order to avoid traffic congestion, each intersection is connected to no more than 3 roads.

Your task is to map Silvermill City by determining all \(N-1\) roads, that is, find all tuples \((A_i, B_i, W_i)\). To achieve this, you can call the function get_distance(int X, int Y) at most \(Q\) times. This function returns the minimal travel time between intersections \(X\) and \(Y\). If you call this function more than \(Q\) times or use an invalid intersection number, your program will immediately terminate with a Wrong Answer verdict.

Note: In this problem, you should not implement the main function. You only need to implement the function find_roads as described below.

All mathematical formulas are rendered in \(\LaTeX\) format.

inputFormat

The function find_roads receives the following parameters:

• int N: number of intersections in the city.
• int Q: maximum allowed number of queries to get_distance.

The function should output three arrays A, B, and W representing the endpoints and weights of the \(N-1\) roads. The roads can be output in any order, and for each road the order of endpoints is arbitrary. Note that array indices start at 0.

outputFormat

The output consists of three arrays A, B, and W (each of size \(N-1\)) which represent the road network of Silvermill City. For every road \(i\) (\(0 \le i \le N-2\)), A[i] and B[i] denote the two intersections that the road connects, and W[i] indicates the travel time (in minutes) required to traverse that road.

sample

3 10
# Hidden tree is a chain: 0-1 (1 minute), 1-2 (1 minute)

0 1 1
1 2 1