재능 있는 바푸코

시간 제한10초메모리 제한512 MB

요약

최대 차수가 3인 트리의 제곱 그래프가 주어질 때, 원래 트리의 인접 리스트를 복원합니다.

난이도: 어려움10점 중 8점
유형: 트리, 그래프, 구현
정답자: 아직 제출이 없습니다

문제

바푸코는 재능 있는 학생이다. 십대지만 지금은 고급 알고리즘을 공부하고 있다. 그녀는 그래프와 트리를 막 배웠다. 오늘 수업의 교수님이 프로그래밍 과제를 내주었다. 과제는 무방향 그래프 $GU = (V, F)$ 로부터 트리 그래프 $GT = (V, E)$ 의 인접 리스트를 복원하는 것이다. $GT$ 와 $GU$ 의 성질은 다음과 같다.

$GT$ 는 트리 그래프다.
$GT$ 와 $GU$ 는 같은 정점 집합 $V = \{1, \ldots, n\}$ 을 가진다.
모든 정점 $v \in V$ 에 대해, $GT$ 에서 $v$ 의 차수는 3 이하다.
간선 $\{u, v\}$ 가 $F$ 에 속하는 것은 $GT$ 에서 $u$ 와 $v$ 의 거리가 1 또는 2일 때이며, 그 경우에만 속한다.

당신은 프로 프로그래머로서 이 과제를 20분 안에 끝내고, 바푸코가 좋아하는 게임 Super Smash Sisters를 하면서 과제가 얼마나 쉬운지 자랑하고 싶다. 해낼 수 있겠는가?

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 각 테스트 케이스의 첫 줄에는 트리의 정점 개수 $n$ 이 주어진다. 이어서 $n$ 개의 줄이 주어지며, $i$ 번째 줄은 $GU$ 에서 정점 $i$ 의 이웃을 나타낸다. 이 줄은 이웃의 개수 $c_i$ 로 시작하고, 이어서 서로 다른 $c_i$ 개의 수 $v_{i,1}, \ldots, v_{i,c_i}$ 가 주어진다. 각 $\{i, v_{i,j}\}$ 는 주어진 그래프 $GU$ 의 간선이다.

출력

각 테스트 케이스마다 트리 $GT$ 의 인접 리스트를 나타내는 $n$ 개의 줄을 출력한다. $i$ 번째 줄에는 정점 $i$ 의 이웃 개수를 출력한 뒤, 이웃을 오름차순으로 출력한다. 수는 공백으로 구분한다.

제한

$7 \le n \le 10^5$
$1 \le T \le 4.5 \times 10^5$
한 입력 파일에 있는 모든 테스트 케이스의 $n$ 의 합은 $3.6 \times 10^6$ 이하다.
각 테스트 케이스에 대해 유일한 트리 $GT$ 를 항상 찾을 수 있다.

예제1

예제 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

예상 출력