La Infraestructura Tecnológica de Castores Industriosos Monitoreados (MITIT, por sus siglas en inglés) está compuesta por $N$ castores numerados del $1$ al $N$. Existen $M$ pares de castores $(u_i, v_i)$, donde inicialmente el castor $u_i$ es responsable de monitorear al castor $v_i$. Cada castor es monitoreado por al menos otro castor.

Busy Beaver, el gerente de MITIT, desea reconfigurar estas relaciones de monitoreo. En una operación, puede tomar un par $(u, v)$ donde el castor $u$ actualmente monitorea al castor $v$ y hacer que el castor $v$ monitoree al castor $u$ en su lugar. Sin embargo, debe asegurarse de que cada castor sea monitoreado por al menos otro castor en todo momento.

La configuración final deseada por Busy Beaver puede describirse mediante una cadena $d$ de longitud $M$, donde $d_i = 0$ si el castor $u_i$ monitorea al castor $v_i$ al final, y $d_i = 1$ si el castor $v_i$ monitorea al castor $u_i$ al final. Encuentre la secuencia más corta de operaciones necesaria para alcanzar esta configuración final, o informe si es imposible.

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^4$). A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $N$ y $M$ ($3 \le N \le M \le 10^5$).

La $i$-ésima de las siguientes $M$ líneas contiene dos enteros $u_i$ y $v_i$ ($1 \le u_i, v_i \le N, u_i \ne v_i$). No existen $1 \le i < j \le M$ tales que $(u_i, v_i) = (u_j, v_j)$ o $(u_i, v_i) = (v_j, u_j)$.

La siguiente línea contiene una cadena $d_1 \dots d_M$, donde $d_i \in \{0, 1\}$ para todo $1 \le i \le M$.

Se garantiza que, tanto en la configuración inicial como en la final, cada castor es monitoreado por al menos otro castor.

Se garantiza que la suma de $N$ en todos los casos de prueba no supera $10^5$.

Se garantiza que la suma de $M$ en todos los casos de prueba no supera $10^5$.

Salida

Para cada caso de prueba, si la tarea es imposible, imprima un único entero $-1$.

De lo contrario, imprima primero un entero $K$, el número de operaciones utilizadas. En la siguiente línea, imprima $K$ enteros $a_1, \dots, a_K$ ($1 \le a_i \le M$), representando que su solución realiza operaciones sobre $(u_{a_i}, v_{a_i})$ en orden.

Puntuación

Para obtener el puntaje completo, $K$ siempre debe ser el número mínimo posible de operaciones. De lo contrario, recibirá el $50\%$ de los puntos de cada subtarea si imprime correctamente cualquier secuencia válida de operaciones donde la suma de $K$ en todos los casos de prueba no supere $10^6$.

• ($50$ puntos) $M \le 300$.
• ($50$ puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

3
4 5
1 2
2 3
3 1
1 4
4 3
11000
6 6
1 2
2 3
3 1
4 5
5 6
6 4
111111
3 3
1 2
2 3
3 1
000

Salida 1

2
2 1
-1
0

Nota

Las operaciones en el primer caso de prueba se muestran a continuación. Tenga en cuenta que realizar las operaciones en el orden opuesto no es aceptable porque el castor $2$ debe ser monitoreado en todo momento.

En el segundo caso de prueba, no es posible alcanzar la configuración final.

En el tercer caso de prueba, no es necesario realizar ninguna operación.