34533번 - Euler Tour Problem

문제

$N$개의 정점으로 이루어진 트리가 주어진다. 각 정점은 1ドル$부터 $N$까지 번호가 매겨져 있고, 루트는 1ドル$번 정점이다.

여러분은 트리의 루트에서 시작해 DFS(Depth-First Search)를 수행했다. 단, 한 정점에서 방문할 수 있는 인접한 자식 정점이 여러 개라면 정점 번호가 작은 정점 순서대로 먼저 방문한다. 그 과정에서 어떤 정점에 처음 진입했을 때 1을, 그 정점에서 빠져나올 때 0을 공책에 기록하고 순서대로 이어 붙였다. 이렇게 만들어진 길이가 2ドルN$인 문자열을 $S$라고 하자.

여러분은 0개 이상 1개 이하의 정점에 대해서 특별히 그 정점의 자식 정점 방문 순서를 임의로 재배열하여 방문할 수 있다. 그 상태에서 이전처럼 DFS를 수행하여 만들어진 문자열을 $S'$이라 하자. 이때 가능한 모든 $S'$ 중, 사전순으로 가장 앞서는 문자열을 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1≤T≤100,円 000)$

각 테스트 케이스의 첫째 줄에 $N$이 주어진다. $(1\le N\le 100,円 000)$

각 테스트 케이스의 둘째 줄에는 $P_1,P_2,\cdots ,P_N$이 공백으로 구분되어 주어지는데 각각 $i$번 정점의 부모는 $P_i$라는 의미다. 단, 1ドル$번 정점의 부모는 존재하지 않으므로 $P_1$은 -1로 주어진다.

모든 테스트 케이스에서 $N$의 합은 100ドル,円 000$을 초과하지 않는다.

출력

각 테스트 케이스마다 가능한 모든 $S'$ 중 사전순으로 가장 앞서는 문자열을 출력한다.

제한

노트

트리는 무방향 사이클이 없는 연결 그래프를 의미한다.