시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 (추가 시간 없음) 512 MB 0 0 0 0.000%

문제

Bafuko is a gifted student. Despite being a teenager, she is studying advanced algorithms now. She just learned about graphs and trees. The instructor of the class gave a programming assignment today. This task is about recovering the adjacency list of a tree graph GT = (V, E) from a given undirected graph GU = (V, F). The properties of GT and GU are listed as follows.

  • GT is a tree graph.
  • GT and GU have the same vertex set V = {1, . . . , n}.
  • For every vertex v ∈ V , the degree of v in GT is at most 3.
  • The edge {u, v} belongs to F if and only if the distance between u and v in GT is either 1 or 2.

You, as a professional programmer, will like to finish the assignment in 20 minutes and brag about how easy it is while playing Bafuko’s favorite game — Super Smash Sisters. Let’s see if you can do it!

입력

First line contains a number T indicating the number of test cases. For each test case, the first line contains a number n indicating the number of vertices in the tree. Then n lines follow. The i-th line descibes the neighbors of i in GU. It is started by ci, the numbers of neighbors of i, then ci distinct numbers vi,1, . . . , vi,ci follow, where {i, v1}, . . . , {i, vci} ∈ F are edges in the given graph GU.

출력

For each test case, please output n lines to describe the adjacency list of the tree graph GT. For the i-th line, please ouput the number of neighbors of i and then the neighbors of i in ascending order. Separate adjacent numbers by a space.

제한

  • 7 ≤ n ≤ 105
  • 1 ≤ T ≤ 4.5 × 105
  • The sum of n’s in all test cases in a single test file is at most 3.6 × 106.
  • For each test case, you can always find a unique tree graph GT.

예제 입력 1

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

예제 출력 1

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