406817: GYM102565 F Predictable Tree

Peter's tree has now come to a stable state, it doesn't give mixed signals anymore and wants to change. Our boy thinks that the best change is a look change, so he will help his friend adjust the colors in its nodes. The tree initially has colour $$$0$$$ in all its nodes, but it doesn't want to change so much. Hence, Peter will colour only a path in the tree with colour $$$1$$$. A colouring of a tree is defined as the sequence of colours in the nodes of the tree taken in increasing order from $$$1$$$ to $$$N$$$.

Everyone knows that this year the number $$$K$$$ is trending, so Peter wants a path such that the final colouring is the $$$K$$$-th lexicographically smallest one. Find the endpoints of this path.

The first line of the input contains a number $$$1 \leq T \leq 10^{18}$$$, the number of tests.

The first line of each test contains 2 integers $$$1 \leq N \leq 500.000$$$ (the number of nodes in the tree) and $$$1 \leq K \leq \frac{N(N+1)}{2}$$$.

The following $$$N-1$$$ lines will each contain a pair of integers ($$$a, b$$$) signifying that there is an edge between node $$$a$$$ and node $$$b$$$ ($$$1 \leq a, b \leq N$$$).

It is guaranteed that the sum of all $$$N$$$ is less than $$$500.000$$$.

The output should contain $$$T$$$ lines, each containing an answer to a test, the endpoints of the path that gives the $$$K$$$-th smallest lexicographically colouring. The endpoints should be printed in non-decreasing order.

7
3 1
1 2
1 3
3 2
1 2
1 3
3 3
1 2
1 3
3 4
1 2
1 3
3 5
1 2
1 3
3 6
1 2
1 3
5 11
3 2
5 4
1 5
1 2

3 3
2 2
1 1
1 3
1 2
2 3
2 5

For the tree containing 3 nodes and edges (1,2) and (1,3) there are 6 different possible paths that each determine a different colouring.

The path (3,3) gives the colouring 001.

The path (2,2) gives the colouring 010.

The path (1,1) gives the colouring 100.

The path (1,3) gives the colouring 101.

The path (1,2) gives the colouring 110.

The path (2,3) gives the colouring 111.