Routing in Singapore's Backbone Network

The Singapore Internet backbone is composed of n network sites uniquely identified by numbers from \(0\) to \(n-1\). There are exactly \(n-1\) bidirectional links (numbered from \(0\) to \(n-2\)) connecting pairs of different sites, so that any two distinct sites are connected by exactly one unique simple path. Two sites connected by a link are said to be neighbors.

A sequence of distinct sites \(a_0, a_1, \ldots, a_p\) is a path from site \(x\) to site \(y\) if and only if \(a_0=x\), \(a_p=y\) and every two consecutive sites in the sequence are neighbors.

Any site \(x\) can generate a data packet addressed to any other site \(y\) (the destination). The packet is routed along the unique simple path from \(x\) to \(y\). When a packet at site \(z\) (with \(z\ne y\)) has destination \(y\), the site \(z\) performs the following two steps:

1. Execute a routing function to determine the neighbor of \(z\) that lies on the unique path from \(z\) to \(y\).
2. Forward the packet to that neighbor.

Because of memory constraints, a site cannot store the full list of network links required in the routing function. To solve this problem, two functions must be implemented:

• label(n, k, u, v): Given the number of sites n, an integer k (with \(k \ge n-1\)), and two arrays u and v (each of size \(n-1\)) representing the links (for each \(i\), link \(i\) connects site \(u[i]\) and site \(v[i]\)), assign each site a unique label in the range \(0\) to \(k-1\>. The returned labels must be a permutation of \(n\) numbers in that range.
• find_next_station(s, t, c): This routing function is installed on every site after the labeling is done. Its parameters are:
  • s: the current site’s label;
  • t: the destination site’s label (with \(t \ne s\));
  • c: an array of labels of all neighbors of site \(s\) in ascending order.
  It should return the label of the neighbor to which the packet is forwarded next (i.e. the neighbor on the unique path from \(s\) to \(t\)).

Note: In the contest system, each test case consists of one or more independent scenarios (each with its own network description). In the first run, the label function is called for every scenario to assign labels. The results are stored and will then be used in the second run when many calls of the find_next_station function are made. In the second run the label function is not called and no static/global information is preserved between these two runs.

Your score for each subtask depends on the maximum label used (the lower the maximum, the better).

---

Implementation details:

// Label function
int[] label(int n, int k, int[] u, int[] v)
{
    // Return an array L of size n such that each L[i] is unique in [0, k-1].
}
// Routing function
int find_next_station(int s, int t, int[] c)
{
// Return a neighbor label from c (neighbors are given in ascending order) such that
// this neighbor lies on the unique path from station s to station t.
}

</p>

Important: The provided sample solution uses a trivial approach that always returns the only neighbor when the degree is 1. For the purposes of this sample, we assume that the test cases are chosen so that each scenario is a 2-node tree. In a real contest, you are encouraged to design a scheme that correctly routes even in larger trees.

inputFormat

The input begins with an integer T (\(T \ge 3\)) indicating the number of scenarios. Then, for each scenario, the following input is provided:

• A line containing two integers: n and k (with \(n \ge 2\) and \(k \ge n-1\)).
• \(n-1\) lines, each with two integers u and v, representing a link between sites u and v.
• A line containing an integer Q, the number of routing queries.
• Then Q lines follow. Each query consists of:
• Two integers s and t indicating the current site label and the destination site label.
• An integer d which is the number of neighbors for site s.
• d integers representing the sorted list of neighbor labels of site s (in ascending order).

Note: In our sample, all scenarios will be 2-node trees so that each site has degree 1. This simplifies the routing function.

outputFormat

For each scenario, first output a line with n integers representing the labels assigned to the sites (in order from site 0 to site \(n-1\)). Then, for each routing query in the scenario, output the label of the next station (as returned by find_next_station) on a separate line.

sample

3
2 10
0 1
2
0 1 1 1
1 0 1 0
2 2
0 1
2
0 1 1 1
1 0 1 0
2 100
0 1
2
0 1 1 1
1 0 1 0

0 1
1
0
0 1
1
0
0 1
1
0

</p>