번영하는 나라 AA는 $1$부터 $n$까지 번호가 붙은 $n$개의 도시와 $n-1$개의 도로로 이루어져 있다. 도로 설계가 잘 되어 있어서 어느 도시에서 출발해도 여러 도로를 지나 원하는 목적지에 도달할 수 있다.

AA의 왕 Dreamoon은 내일 모든 도시의 치안을 점검하려고 경로 계획을 세웠다. 이 경로는 AA의 수도인 도시 $1$에서 출발하여 도시 $1$로 돌아오며 $2\times n-2$개의 간선을 지나는 경로이다. 기록하기 편하도록 Dreamoon은 경로에 있는 도시 번호를 순서대로 종이에 적었다.

그런데 안타깝게도 Dreamoon이 종이에 밀크티를 쏟아서 연속된 몇 개의 번호가 이제 잘 보이지 않는다. 좋은 여행을 할 수 있도록 이 흐릿한 번호들을 복원해 달라고 부탁한다.

해가 여러 개이면 사전 순으로 가장 작은 해를 출력하라. 주어진 입력에 대해 적어도 하나의 해가 있음이 보장된다.

입력

첫 줄에는 테스트 케이스의 개수인 정수 $T$ 하나가 주어진다. 아래는 입력 데이터 세트의 설명이다.

각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 AA의 도시 수인 정수 $n$ 하나가 주어진다. 둘째 줄에는 $0$ 이상 $n$ 이하의 정수 $2\times n-1$개가 주어진다. $i$번째 수는 경로의 $i$번째 도시를 나타낸다. $i$번째 수가 $0$이면 쏟아진 밀크티 때문에 그 번호를 알아볼 수 없다는 뜻이다. 모든 $0$은 연속해서 나타나며, 적어도 하나의 $0$이 있음이 보장된다.

제한

• $1\le T\le30\,000$.

• $1\le n\le300\,000$.

• 도시 번호는 $1$부터 $n$까지이다.

• Dreamoon이 종이에 적은 도시 번호 중 적어도 하나가 흐릿하며, 흐릿한 번호들은 모두 연속해 있다.

• 모든 테스트 케이스에 대한 $n$의 합은 $300\,000$을 넘지 않는다.

출력

각 테스트 케이스에 대해 복원한 경로를 나타내는 $1$ 이상 $n$ 이하의 수 $2\times n-1$개를 한 줄에 출력하라. 해가 여러 개이면 사전 순으로 가장 작은 해를 출력해야 한다. 주어진 입력에 대해 적어도 하나의 해가 있음이 보장된다.

예제

입력 1

9
5
1 2 3 2 0 2 1 5 1
5
1 2 3 0 0 2 1 5 1
5
1 2 0 0 0 2 1 5 1
5
1 2 0 0 0 0 1 5 1
5
1 0 0 0 0 0 1 5 1
5
1 0 0 0 0 0 0 5 1
5
1 0 0 0 0 0 0 0 1
5
1 0 0 0 0 0 0 0 0
5
0 0 0 0 0 0 0 0 0

출력 1

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