To zadanie jest interaktywne.

Na planecie KSA znajduje się $N$ wysp. Wyspy są ponumerowane od $1$ do $N$, a wyspa $i$ posiada $w_i$ zasobów. Żadne dwie różne wyspy nie mają takiej samej ilości zasobów. Pomiędzy wyspami istnieje $N-1$ dwukierunkowych przejść podwodnych i zagwarantowane jest, że z każdej wyspy można dotrzeć do każdej innej, korzystając wyłącznie z przejść podwodnych. Innymi słowy, struktura utworzona przez wyspy i przejścia podwodne jest drzewem.

Po uświadomieniu sobie, że przejścia podwodne na planecie KSA nie są widoczne z innych planet, Alice, królowa planety KSA, planuje dodatkowo wybudować $N-1$ dwukierunkowych mostów naziemnych łączących pary wysp. Używając tylko tych mostów, również musi być możliwe podróżowanie między dowolnymi dwiema wyspami. Oznacza to, że struktura mostów również musi tworzyć drzewo.

Gdy Alice zakończy budowę mostów, Bob, król planety Automata, zaczyna próbować odkryć informacje. W tym momencie numery wysp są dowolnie przypisywane ponownie i od tego momentu każdy numer wyspy, który Bob obserwuje lub wykorzystuje, podlega temu systemowi ponownej numeracji.

Bob musi wyznaczyć $x(i,j)$ dla wszystkich $1 \le i,j \le N$, patrząc tylko na mosty naziemne zbudowane przez Alice, gdzie:

Tutaj numer wyspy startowej $i$, docelowej $j$ oraz numer wyspy z maksymalną ilością zasobów opierają się na systemie ponownej numeracji. Ścieżka od wyspy o numerze $i$ do wyspy o numerze $j$ obejmuje zarówno wyspę o numerze $i$, jak i wyspę o numerze $j$.

Przed wyznaczeniem wszystkich wartości $x(i,j)$, Bob może zadać następujące pytanie maksymalnie $100$ razy, aby uzyskać dodatkowe informacje:

• `?` $i$ $j$ : Jaka jest wartość $x(i,j)$?

Ponieważ komunikacja międzyplanetarna jest bardzo kosztowna, mniejsza liczba pytań skutkuje wyższym wynikiem.

Twój program jest wykonywany dwukrotnie dla każdego zestawu danych sędziowskich. W pierwszym wykonaniu musi odegrać rolę Alice, a w drugim wykonaniu musi odegrać rolę Boba.

Pierwsza linia zawiera liczbę całkowitą $S$, wskazującą krok wykonania. $S=1$ oznacza grę jako Alice, a $S=2$ oznacza grę jako Bob.

Wejście składa się z jednego lub więcej przypadków testowych. Druga linia zawiera liczbę przypadków testowych, $T$. Każdy przypadek testowy jest podany w następujący sposób.

Pierwsza linia zawiera liczbę wysp, $N$.

Druga linia zawiera $N$ liczb całkowitych oddzielonych spacjami $w_1, w_2, \cdots, w_N$.

Każda z kolejnych $N-1$ linii zawiera dwie liczby całkowite oddzielone spacjami $u$, $v$, będące końcami przejścia podwodnego.

Wypisz $N-1$ linii, z których każda zawiera dwie liczby całkowite oddzielone spacjami $u$ i $v$, będące końcami mostu naziemnego do wybudowania. Kolejność, w jakiej wypisywane są mosty, nie ma znaczenia, podobnie jak kolejność dwóch końców w każdym moście.

Wejście składa się z jednego lub więcej przypadków testowych. Druga linia zawiera liczbę przypadków testowych, $T$. Każdy przypadek testowy jest podany w następujący sposób.

Pierwsza linia zawiera liczbę wysp, $N$.

Każda z kolejnych $N-1$ linii zawiera dwie liczby całkowite oddzielone spacjami $u$, $v$, będące końcami mostu naziemnego zbudowanego przez Alice. Zauważ, że $u$ i $v$ używają systemu ponownej numeracji, a kolejność mostów otrzymywanych przez Boba może różnić się od kolejności, w jakiej wypisała je Alice.

Aby uzyskać dodatkowe informacje, po wypisaniu poniższego zapytania, w następnej linii pojawi się wartość $x(i,j)$. To zapytanie można zadać maksymalnie $100$ razy na przypadek testowy.

• `?` $i$ $j$ ($1 \le i, j \le N$)

Aby przesłać odpowiedź, wypisz `!` , a następnie wypisz odpowiedź w kolejnych $N$ liniach. W $i$-tej z $N$ linii należy wypisać $x(i,1), x(i,2), \cdots, x(i,N)$ oddzielone spacjami. To zapytanie nie liczy się jako pytanie, a interakcja dla danego przypadku testowego kończy się natychmiast po wypisaniu.

Jeśli interakcja kończy się dla przypadku testowego, który nie jest ostatnim, należy natychmiast przejść do następnego przypadku testowego. Jeśli interakcja dla ostatniego przypadku testowego kończy się, program musi natychmiast zakończyć działanie.

Jeśli jednak w pojedynczym przypadku testowym zadano więcej niż $100$ pytań, odpowiedzią na zapytanie będzie `-1` , co oznacza przekroczenie dozwolonej liczby pytań. W takim przypadku program musi natychmiast zakończyć działanie, a wynik zostanie oceniony jako Błędna Odpowiedź (Wrong Answer).

Ograniczenia

• $S \in \{1, 2 \}$
• $1 \le T \le 100$
• $2 \le N \le 100$
• $1 \le u < v \le N$
• $1 \le w_i \le 10^9$
• Jeśli $i \ne j$, to $w_i \neq w_j$

Punktacja

Dla każdego zestawu danych sędziowskich, niech $Q$ będzie maksymalną liczbą pytań zadanych we wszystkich przypadkach testowych. Wynik dla danego zestawu danych jest określony w następujący sposób:

Wynik twojego zgłoszenia to minimalny wynik ze wszystkich zestawów danych sędziowskich. Mogą jednak wystąpić nieoczekiwane rezultaty, jeśli rozwiązanie nie zostanie wypisane poprzez poprawne interakcje w ramach podanych ograniczeń zadania.

Przykład

Wejście 1

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

2
10 1
1 2

Wyjście 1

1 4
2 3
3 4

1 2

Wejście 2

2
2
4
1 3
1 4
2 3

4
1

2
1 2

2

Wyjście 2

? 2 3

? 1 2

!
1 1 1 1
1 2 4 4
1 4 3 4
1 4 4 4

? 1 2

!
1 2
2 2

Uwagi

W przykładzie 1, ponieważ $S = 1$, twój program musi odegrać rolę Alice.

W przykładzie 2, ponieważ $S = 2$, twój program musi odegrać rolę Boba.

W pierwszym przypadku testowym wierzchołki $1, 2, 3, 4$ z pierwszego wykonania zostały ponownie przypisane odpowiednio do wierzchołków $2, 4, 1, 3$.

W drugim przypadku testowym wierzchołki $1, 2$ z pierwszego wykonania zostały ponownie przypisane odpowiednio do wierzchołków $2, 1$.

Musisz opróżnić bufor wyjściowy natychmiast po wypisaniu czegokolwiek. Aby to zrobić, możesz użyć:

• C --- `fflush(stdout)`
• C++ --- `std::cout.flush()`
• Python --- `sys.stdout.flush()`
• Java --- `System.out.flush()`
• sprawdź dokumentację dla innych języków.

Zauważ również, że puste linie w przykładowym wejściu i wyjściu służą przejrzystości i nie występują w rzeczywistej interakcji.