Istnieje zamożny kraj AA, składający się z $n$ miast (ponumerowanych od $1$ do $n$) oraz $n-1$ dróg. Dzięki dobremu projektowi dróg z dowolnego miasta można, przechodząc kilkoma drogami, dotrzeć do wybranego celu.

Król AA, Dreamoon, chce jutro sprawdzić porządek i bezpieczeństwo we wszystkich miastach, więc zaplanował trasę. Jest to ścieżka o $2\times n-2$ krawędziach, zaczynająca się i kończąca w mieście $1$ (stolicy AA). Aby ułatwić zapis, Dreamoon wypisał na papierze po kolei numery miast na tej ścieżce.

Niestety Dreamoon rozlał na papierze herbatę z mlekiem i pewien ciąg kolejnych numerów stał się nieczytelny. Prosi cię o odtworzenie tych numerów, aby podróż przebiegła dobrze.

Jeśli istnieje wiele rozwiązań, wypisz najmniejsze leksykograficznie. Gwarantowane jest, że dla danego wejścia istnieje co najmniej jedno rozwiązanie.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $T$, liczbę przypadków testowych. Poniżej opisano zestawy danych wejściowych.

Każdy przypadek testowy składa się z dwóch wierszy. Pierwszy zawiera jedną liczbę całkowitą $n$, liczbę miast w AA. Drugi zawiera $2\times n-1$ liczb całkowitych od $0$ do $n$; $i$-ta liczba oznacza $i$-te miasto na ścieżce. Jeśli $i$-ta liczba to $0$, numer jest nieczytelny z powodu rozlanej herbaty z mlekiem. Wejście gwarantuje, że wszystkie zera występują kolejno i jest co najmniej jedno zero.

Ograniczenia

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

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

• Miasta są ponumerowane od $1$ do $n$.

• Co najmniej jeden numer miasta zapisany przez Dreamoon na papierze jest nieczytelny, a wszystkie nieczytelne numery występują kolejno.

• Suma $n$ po wszystkich przypadkach testowych nie przekracza $300\,000$.

Wyjście

Dla każdego przypadku testowego wypisz w jednym wierszu $2\times n-1$ liczb od $1$ do $n$, opisujących odtworzoną ścieżkę. Pamiętaj, by w razie wielu rozwiązań wypisać najmniejsze leksykograficznie. Gwarantowane jest, że dla danego wejścia istnieje co najmniej jedno rozwiązanie.

Przykład

Wejście 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

Wyjście 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