Euler Tour Problem

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

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

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