El Pueblo Colorido es un popular destino turístico. Tiene \(2n\) casas, numeradas del \(1\) al \(2n\). Cada casa tiene uno de \(n\) colores, numerados del \(1\) al \(n\). Casualmente, para cada uno de los \(n\) colores, exactamente dos casas están pintadas con ese color.

Hay \(2n-1\) caminos bidireccionales en el Pueblo Colorido. Cada camino conecta dos casas distintas, y es posible llegar desde cualquier casa a cualquier otra usando estos caminos.

Catalina está planeando un viaje al Pueblo Colorido. Su tiempo es limitado, así que quiere elegir un conjunto \(S\) de \(n\) casas para visitar, con exactamente una casa de cada color. Sin embargo, como Catalina también necesita moverse entre las casas, el conjunto de casas que va a visitar debe ser \(\textbf{conexo}\). En otras palabras, debe ser posible llegar desde cualquier casa en \(S\) a cualquier otra casa en \(S\) usando los caminos, visitando únicamente casas de \(S\) en el trayecto.

Ayudá a Catalina a encontrar un conjunto conexo \(S\) de \(n\) casas, una de cada color, o reportá que dicho conjunto no existe.

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba \(t\) (\(1 \le t \le 10^5\)). A continuación se describe cada caso de prueba.

La primera línea de cada caso de prueba contiene un único entero \(n\) (\(1 \le n \le 10^5\)).

La segunda línea contiene \(2n\) enteros \(c_1, c_2, \ldots, c_{2n}\), que denotan los colores de las casas del Pueblo Colorido (\(1 \le c_i \le n\)). Cada entero del \(1\) al \(n\) aparece exactamente dos veces en esta línea.

La \(i\)-ésima de las siguientes \(2n-1\) líneas contiene dos enteros \(u_i\) y \(v_i\), que denotan las casas conectadas por el \(i\)-ésimo camino (\(1 \le u_i, v_i \le 2n\); \(u_i \ne v_i\)).

Se garantiza que la suma de \(n\) sobre todos los casos de prueba no excede \(10^5\).

Salida

Para cada caso de prueba, imprimí un único entero \(-1\) si el conjunto requerido no existe.

En caso contrario, imprimí \(n\) enteros distintos \(s_1, s_2, \ldots, s_n\) en cualquier orden, que denoten un conjunto conexo \(S\) de \(n\) casas, una de cada color (\(1 \le s_i \le 2n\)). Si hay múltiples respuestas, imprimí cualquiera de ellas.

Ejemplos

Entrada

2
4
1 3 1 3 4 4 2 2
1 6
5 3
2 4
7 1
7 5
5 8
2 5
3
1 1 2 2 3 3
1 2
2 3
3 4
4 5
5 6

Salida

2 3 5 7
-1