L'infrastructure technologique des castors industrieux surveillés (MITIT) est composée de $N$ castors numérotés de $1$ à $N$. Il existe $M$ paires de castors $(u_i, v_i)$, où initialement, le castor $u_i$ est responsable de la surveillance du castor $v_i$. Chaque castor est surveillé par au moins un autre castor.

Busy Beaver, le gestionnaire de MITIT, souhaite reconfigurer ces relations de surveillance. En une opération, il peut choisir une paire $(u, v)$ où le castor $u$ surveille actuellement le castor $v$ et faire en sorte que le castor $v$ surveille le castor $u$ à la place. Cependant, il doit s'assurer que chaque castor est surveillé par au moins un autre castor à tout moment.

La configuration finale souhaitée par Busy Beaver peut être décrite par une chaîne $d$ de longueur $M$, où $d_i = 0$ si le castor $u_i$ surveille le castor $v_i$ à la fin et $d_i = 1$ si le castor $v_i$ surveille le castor $u_i$ à la fin. Trouvez une séquence d'opérations la plus courte possible pour atteindre cette configuration finale, ou indiquez qu'il est impossible d'y parvenir.

Entrée

Chaque test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $T$ ($1 \le T \le 10^4$). La description des cas de test suit.

La première ligne de chaque cas de test contient deux entiers $N$ et $M$ ($3 \le N \le M \le 10^5$).

La $i$-ième des $M$ lignes suivantes contient deux entiers $u_i$ et $v_i$ ($1 \le u_i, v_i \le N, u_i \ne v_i$). Il n'existe pas de $1 \le i < j \le M$ tel que $(u_i, v_i) = (u_j, v_j)$ ou $(u_i, v_i) = (v_j, u_j)$.

La ligne suivante contient une chaîne $d_1 \dots d_M$, où $d_i \in \{0, 1\}$ pour tout $1 \le i \le M$.

Il est garanti que dans les configurations initiale et finale, chaque castor est surveillé par au moins un autre castor.

Il est garanti que la somme de $N$ sur tous les cas de test ne dépasse pas $10^5$.

Il est garanti que la somme de $M$ sur tous les cas de test ne dépasse pas $10^5$.

Sortie

Pour chaque cas de test, si la tâche est impossible, affichez un seul entier $-1$.

Sinon, affichez d'abord un entier $K$, le nombre d'opérations effectuées. Sur la ligne suivante, affichez $K$ entiers $a_1, \dots, a_K$ ($1 \le a_i \le M$), indiquant que votre solution effectue les opérations sur $(u_{a_i}, v_{a_i})$ dans l'ordre.

Barème

Pour obtenir tous les points, $K$ doit toujours être le nombre minimal possible d'opérations. Sinon, vous recevrez $50 \%$ des points pour chaque sous-tâche si vous affichez correctement une séquence valide d'opérations où la somme de $K$ sur tous les cas de test ne dépasse pas $10^6$.

• ($50$ points) $M \le 300$.
• ($50$ points) Aucune contrainte supplémentaire.

Example

Entrée 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

Sortie 1

2
2 1 
-1
0

Note

Les opérations du premier cas de test sont illustrées ci-dessous. Notez que l'exécution des opérations dans l'ordre inverse n'est pas acceptable car le castor $2$ doit être surveillé à tout moment.

Dans le deuxième cas de test, il n'est pas possible d'atteindre la configuration finale.

Dans le troisième cas de test, aucune opération ne doit être effectuée.