CSES - Datatähti Open 2021 - Distances
  • Time limit: 1.00 s
  • Memory limit: 512 MB

You are given a tree (i.e. an acyclic connected graph) which has nn vertices. The distance between two vertices is the number of edges in the shortest path between them.

Your task is to find an order of the vertices where the distance between adjacent vertices is at most 33.

Input

The first line of input consists of an integer tt: the number of test cases.

After that, the first line of each test contains the number of nodes nn. The following n1n-1 lines describe the edges of the tree.

Output

For each test print nn numbers: the order of the vertices. You may print any valid solution.

Example

Input:

2
4
1 2
1 3
1 4
3
1 2
2 3

Output:

1 2 3 4
2 1 3

Subtask 1 (29 points)

  • 1t1001 \le t \le 100
  • 1n81 \le n \le 8

Subtask 2 (71 points)

  • 1t1001 \le t \le 100
  • 1n1001 \le n \le 100