Este es un problema interactivo.

En el planeta KSA hay $N$ islas. Las islas están numeradas del $1$ al $N$, y la isla $i$ tiene una cantidad $w_i$ de recursos. No hay dos islas distintas que tengan la misma cantidad de recursos. Entre las islas hay $N-1$ pasajes submarinos bidireccionales, y se garantiza que cualquier par de islas puede conectarse entre sí utilizando únicamente estos pasajes. En otras palabras, la estructura formada por las islas y los pasajes submarinos es un árbol.

Tras darse cuenta de que los pasajes submarinos del planeta KSA no son visibles desde otros planetas, Alice, el rey del planeta KSA, planea construir adicionalmente $N-1$ puentes terrestres bidireccionales que conecten pares de islas. Utilizando únicamente estos puentes, también debe ser posible viajar entre cualquier par de islas. Es decir, la estructura de los puentes también debe formar un árbol.

Una vez que Alice termina de construir los puentes, Bob, el rey del planeta Automata, comienza a intentar descubrir información. En este momento, los números de las islas se reasignan arbitrariamente y, a partir de entonces, todos los números de isla que Bob observa o utiliza siguen este sistema de numeración reasignado.

Bob debe determinar $x(i,j)$ para todo $1 \le i,j \le N$ observando únicamente los puentes terrestres construidos por Alice, donde:

Aquí, el número de la isla de inicio $i$, el número de la isla de destino $j$ y el número de la isla con la mayor cantidad de recursos se basan en el sistema de numeración reasignado. El camino desde la isla número $i$ hasta la isla número $j$ incluye tanto a la isla número $i$ como a la isla número $j$.

Antes de determinar todos los valores de $x(i,j)$, Bob puede realizar la siguiente pregunta como máximo $100$ veces para obtener información adicional:

• `?` $i$ $j$ : ¿Cuál es $x(i,j)$?

Dado que la comunicación interplanetaria es muy costosa, realizar menos preguntas resulta en una puntuación más alta.

Su programa se ejecuta dos veces para cada conjunto de datos de prueba. En la primera ejecución, debe desempeñar el papel de Alice, y en la segunda ejecución, debe desempeñar el papel de Bob.

La primera línea contiene un entero $S$, que indica el paso de ejecución. $S=1$ significa jugar como Alice, y $S=2$ significa jugar como Bob.

Entrada

La entrada consta de uno o más casos de prueba. La segunda línea contiene el número de casos de prueba, $T$. Cada caso de prueba se proporciona de la siguiente manera.

La primera línea contiene el número de islas, $N$.

La segunda línea contiene $N$ enteros separados por espacios $w_1, w_2, \cdots, w_N$.

Cada una de las siguientes $N-1$ líneas contiene dos enteros separados por espacios $u$, $v$, los extremos de un pasaje submarino.

Salida

Imprima $N-1$ líneas, cada una conteniendo dos enteros separados por espacios $u$ y $v$ que representan los extremos de un puente terrestre a construir. El orden en el que se imprimen los puentes no importa, y el orden de los dos extremos en cada puente tampoco importa.

Interacción

La entrada consta de uno o más casos de prueba. La segunda línea contiene el número de casos de prueba, $T$. Cada caso de prueba se proporciona de la siguiente manera.

La primera línea contiene el número de islas, $N$.

Cada una de las siguientes $N-1$ líneas contiene dos enteros separados por espacios $u$, $v$, los extremos de un puente terrestre construido por Alice. Tenga en cuenta que $u$ y $v$ utilizan el sistema de numeración reasignado, y el orden de los puentes que recibe Bob puede diferir del orden en que Alice los imprimió.

Para obtener información adicional, cuando se imprima la siguiente consulta, la siguiente línea contendrá el valor de $x(i,j)$. Esta consulta se puede utilizar como máximo $100$ veces por caso de prueba.

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

Para enviar una respuesta, imprima `!` , y luego imprima la respuesta en las siguientes $N$ líneas. En la línea $i$-ésima de las $N$ líneas, se deben imprimir $x(i,1), x(i,2), \cdots, x(i,N)$ separados por espacios. Esta consulta no cuenta como una pregunta, y la interacción para el caso de prueba correspondiente termina inmediatamente después de imprimir.

Si la interacción termina para un caso de prueba que no es el último, debe proceder inmediatamente al siguiente caso de prueba. Si la interacción para el caso de prueba final termina, el programa debe finalizar inmediatamente.

Sin embargo, si se realizaron más de $100$ preguntas en un solo caso de prueba, la respuesta a la consulta se dará como `-1` , lo que indica que se excedió el número permitido de preguntas. En este caso, su programa debe finalizar inmediatamente y el resultado será juzgado como Respuesta Incorrecta (Wrong Answer).

Restricciones

• $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$, entonces $w_i \neq w_j$

Puntuación

Para cada conjunto de datos de prueba, sea $Q$ el número máximo de preguntas realizadas entre todos los casos de prueba. La puntuación para ese conjunto de datos se determina de la siguiente manera:

La puntuación de su envío es la puntuación mínima obtenida en todos los conjuntos de datos de prueba. Sin embargo, pueden ocurrir resultados inesperados si no imprime la solución a través de las interacciones adecuadas dentro de las limitaciones del problema proporcionado.

Ejemplos

Entrada 1

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



2
10 1
1 2

Salida 1

1 4
2 3
3 4



1 2

Entrada 2

2
2
4
1 3
1 4
2 3

4

1





2
1 2

2

Salida 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

Nota

En el Ejemplo 1, dado que $S = 1$, su programa debe desempeñar el papel de Alice.

En el Ejemplo 2, dado que $S = 2$, su programa debe desempeñar el papel de Bob.

En el primer caso de prueba, los vértices $1, 2, 3, 4$ de la primera ejecución fueron reasignados a los vértices $2, 4, 1, 3$, respectivamente.

En el segundo caso de prueba, los vértices $1, 2$ de la primera ejecución fueron reasignados a los vértices $2, 1$, respectivamente.

Debe vaciar (flush) la salida inmediatamente después de imprimir algo. Para vaciar puede usar:

• C --- `fflush(stdout)`
• C++ --- `std::cout.flush()`
• Python --- `sys.stdout.flush()`
• Java --- `System.out.flush()`
• consulte la documentación para otros lenguajes.

Además, tenga en cuenta que las líneas vacías en la entrada y salida de ejemplo son por claridad y no ocurren en la interacción real.