当前没有测试数据。

题目描述

ZYB is a smart guy. One day he learns a new method for representing trees: Euler tour technique (ETT).

You can find more details about ETT on this web page:

https://en.wikipedia.org/wiki/Euler_tour_technique.
https://blog.nowcoder.net/n/7afe88dc36ef4649b4de941f08abf576

If we use vertices rather than edges in ETT, then any tree with $\ N$ vertices corresponds to a sequence of length $\ 2N-1$, let's call it the vertex-ETT sequence.

In the beginning, ZYB generates a tree (the root of that tree is always 1) and writes down its vertex-ETT sequence. However, he spilt ink onto the paper by mistake and some numbers were covered in ink. Can you help him to restore the sequence?

输入格式

There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case, the first line contains a integer $1 \leq N \leq 2.5 \times 10^5$, while the second line contains an integer sequence a( $1 \leq a_i \leq N$ or $a_i=-1$ , which means this number was covered by the ink) of length $\ 2N-1$, the vertex-ETT sequence.

it is guaranteed that at least one valid sequence exists. It's guaranteed that the sum of $\ N$ of all test cases will not exceed $\ 500000$. Due to the large size of the input, it's recommended to use a fast way to read the input.

输出格式

For each case, print $\ 2N-1$ space-separated integers, the recovered sequence. If there are multiple solutions, print any of them.

样例

样例输入 1

2
3
1 2 1 -1 1
3
-1 2 3 -1 1

样例输出 1

1 2 1 3 1
1 2 3 2 1