Ceci est un problème interactif.

Sur la planète KSA, il y a $N$ îles. Les îles sont numérotées de $1$ à $N$, et l'île $i$ possède une quantité $w_i$ de ressources. Aucune paire d'îles distinctes ne possède la même quantité de ressources. Entre les îles, il existe $N-1$ passages sous-marins bidirectionnels, et il est garanti que deux îles quelconques peuvent être reliées l'une à l'autre en utilisant uniquement ces passages sous-marins. En d'autres termes, la structure formée par les îles et les passages sous-marins est un arbre.

Après avoir réalisé que les passages sous-marins de la planète KSA ne sont pas visibles depuis d'autres planètes, Alice, la reine de la planète KSA, prévoit de construire en plus $N-1$ ponts terrestres bidirectionnels reliant des paires d'îles. En utilisant uniquement ces ponts, il doit également être possible de voyager entre deux îles quelconques. C'est-à-dire que la structure des ponts doit également former un arbre.

Une fois qu'Alice a terminé la construction des ponts, Bob, le roi de la planète Automata, commence à essayer de découvrir des informations. À ce moment-là, les numéros des îles sont réassignés arbitrairement, et à partir de là, chaque numéro d'île que Bob observe ou utilise suit ce système de numérotation réassigné.

Bob doit déterminer $x(i,j)$ pour tout $1 \le i,j \le N$ en observant uniquement les ponts terrestres construits par Alice, où :

Ici, le numéro de l'île de départ $i$, le numéro de l'île de destination $j$, et le numéro de l'île possédant la quantité maximale de ressources sont tous basés sur le système de numérotation réassigné. Le chemin de l'île numéro $i$ à l'île numéro $j$ inclut à la fois l'île numéro $i$ et l'île numéro $j$.

Avant de déterminer toutes les valeurs de $x(i,j)$, Bob peut poser la question suivante au plus $100$ fois pour obtenir des informations supplémentaires :

• `?` $i$ $j$ : Quelle est la valeur de $x(i,j)$ ?

Comme la communication interplanétaire est très coûteuse, un nombre réduit de questions permet d'obtenir un meilleur score.

Votre programme est exécuté deux fois pour chaque donnée de test. Lors de la première exécution, il doit jouer le rôle d'Alice, et lors de la seconde exécution, il doit jouer le rôle de Bob.

La première ligne contient un entier $S$, indiquant l'étape de l'exécution. $S=1$ signifie jouer le rôle d'Alice, et $S=2$ signifie jouer le rôle de Bob.

Entrée

L'entrée consiste en un ou plusieurs cas de test. La deuxième ligne contient le nombre de cas de test, $T$. Chaque cas de test est donné comme suit.

La première ligne contient le nombre d'îles, $N$.

La deuxième ligne contient $N$ entiers séparés par des espaces $w_1, w_2, \cdots, w_N$.

Chacune des $N-1$ lignes suivantes contient deux entiers séparés par des espaces $u$, $v$, les extrémités d'un passage sous-marin.

Sortie

Affichez $N-1$ lignes, chacune contenant deux entiers séparés par des espaces $u$ et $v$ qui sont les extrémités d'un pont terrestre à construire. L'ordre dans lequel les ponts sont affichés n'a pas d'importance, et l'ordre des deux extrémités dans chaque pont n'a pas non plus d'importance.

Interaction

L'entrée consiste en un ou plusieurs cas de test. La deuxième ligne contient le nombre de cas de test, $T$. Chaque cas de test est donné comme suit.

La première ligne contient le nombre d'îles, $N$.

Chacune des $N-1$ lignes suivantes contient deux entiers séparés par des espaces $u$, $v$, les extrémités d'un pont terrestre construit par Alice. Notez que $u$ et $v$ utilisent le système de numérotation réassigné, et que l'ordre des ponts que Bob reçoit peut différer de l'ordre dans lequel Alice les a affichés.

Pour obtenir des informations supplémentaires, lorsque la requête suivante est affichée, la ligne suivante contiendra la valeur de $x(i,j)$. Cette requête peut être utilisée au plus $100$ fois par cas de test.

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

Pour soumettre une réponse, affichez `!` , puis affichez la réponse sur les $N$ lignes suivantes. Sur la $i$-ème des $N$ lignes, $x(i,1), x(i,2), \cdots, x(i,N)$ doivent être affichés séparés par des espaces. Cette requête ne compte pas comme une question, et l'interaction pour le cas de test correspondant se termine immédiatement après l'affichage.

Si l'interaction se termine pour un cas de test qui n'est pas le dernier, elle doit immédiatement passer au cas de test suivant. Si l'interaction pour le dernier cas de test se termine, le programme doit se terminer immédiatement.

Cependant, si plus de $100$ questions ont été posées dans un seul cas de test, la réponse à la requête sera `-1` , indiquant que le nombre autorisé de questions a été dépassé. Dans ce cas, votre programme doit se terminer immédiatement, et le résultat sera jugé comme une réponse incorrecte (Wrong Answer).

Contraintes

• $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$
• Si $i \ne j$, alors $w_i \neq w_j$

Sous-tâches

Pour chaque donnée de test, soit $Q$ le nombre maximum de questions posées parmi tous les cas de test. Le score pour cette donnée de test est déterminé comme suit :

Le score de votre soumission est le score minimum sur tous les jeux de données de test. Cependant, des résultats inattendus peuvent se produire si vous n'affichez pas la solution via les interactions appropriées dans les limites du problème fournies.

Exemples

Entrée 1

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

Sortie 1

1 4
2 3
3 4
1 2

Entrée 2

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

Sortie 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

Remarque

Dans l'exemple 1, puisque $S = 1$, votre programme doit jouer le rôle d'Alice.

Dans l'exemple 2, puisque $S = 2$, votre programme doit jouer le rôle de Bob.

Dans le premier cas de test, les sommets $1, 2, 3, 4$ de la première exécution ont été réassignés aux sommets $2, 4, 1, 3$ respectivement.

Dans le second cas de test, les sommets $1, 2$ de la première exécution ont été réassignés aux sommets $2, 1$ respectivement.

Vous devez vider (flush) la sortie immédiatement après avoir affiché quelque chose. Pour vider la sortie, vous pouvez utiliser :

• C --- `fflush(stdout)`
• C++ --- `std::cout.flush()`
• Python --- `sys.stdout.flush()`
• Java --- `System.out.flush()`
• Consultez la documentation pour les autres langages.

De plus, notez que les lignes vides dans l'entrée et la sortie des exemples sont présentes pour des raisons de clarté et n'apparaissent pas dans l'interaction réelle.