Infrastruktura Technologiczna Monitorowanych Pracowitych Bobrów (MITIT) składa się z $N$ bobrów o numerach $1, \dots, N$. Istnieje $M$ par bobrów $(u_i, v_i)$, gdzie początkowo bóbr $u_i$ jest odpowiedzialny za monitorowanie bobra $v_i$. Każdy bóbr jest monitorowany przez co najmniej jednego innego bobra.

Busy Beaver, menedżer MITIT, chciałby zmienić te relacje monitorowania. W jednej operacji może wybrać parę $(u, v)$, w której bóbr $u$ aktualnie monitoruje bobra $v$, i sprawić, by zamiast tego bóbr $v$ monitorował bobra $u$. Musi jednak zapewnić, aby każdy bóbr był przez cały czas monitorowany przez co najmniej jednego innego bobra.

Pożądana konfiguracja końcowa Busy Beavera może być opisana ciągiem $d$ o długości $M$, gdzie $d_i = 0$, jeśli bóbr $u_i$ monitoruje bobra $v_i$ na końcu, oraz $d_i = 1$, jeśli bóbr $v_i$ monitoruje bobra $u_i$ na końcu. Znajdź najkrótszą sekwencję operacji niezbędną do osiągnięcia tej konfiguracji końcowej lub zgłoś, że jest to niemożliwe.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia zawiera liczbę przypadków testowych $T$ ($1 \le T \le 10^4$). Następnie podane są opisy przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera dwie liczby całkowite $N$ i $M$ ($3 \le N \le M \le 10^5$).

$i$-ta z kolejnych $M$ linii zawiera dwie liczby całkowite $u_i$ i $v_i$ ($1 \le u_i, v_i \le N, u_i \ne v_i$). Nie istnieją takie $1 \le i < j \le M$, że $(u_i, v_i) = (u_j, v_j)$ lub $(u_i, v_i) = (v_j, u_j)$.

Następna linia zawiera ciąg $d_1 \dots d_M$, gdzie $d_i \in \{0, 1\}$ dla wszystkich $1 \le i \le M$.

Gwarantuje się, że zarówno w konfiguracji początkowej, jak i końcowej, każdy bóbr jest monitorowany przez co najmniej jednego innego bobra.

Gwarantuje się, że suma $N$ we wszystkich przypadkach testowych nie przekracza $10^5$.

Gwarantuje się, że suma $M$ we wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego, jeśli zadanie jest niemożliwe, wypisz pojedynczą liczbę całkowitą $-1$.

W przeciwnym razie najpierw wypisz liczbę całkowitą $K$, liczbę wykonanych operacji. W następnej linii wypisz $K$ liczb całkowitych $a_1, \dots, a_K$ ($1 \le a_i \le M$), oznaczających, że rozwiązanie wykonuje operacje na $(u_{a_i}, v_{a_i})$ w podanej kolejności.

Punktacja

Aby uzyskać pełną liczbę punktów, $K$ powinno zawsze być minimalną możliwą liczbą operacji. W przeciwnym razie otrzymasz $50\%$ punktów za każde podzadanie, jeśli poprawnie wypiszesz dowolną poprawną sekwencję operacji, w której suma $K$ we wszystkich przypadkach testowych nie przekracza $10^6$.

• (50 punktów) $M \le 300$.
• (50 punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 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

Wyjście 1

2
2 1
-1
0

Uwagi

Zauważ, że wykonanie operacji w odwrotnej kolejności nie jest dopuszczalne, ponieważ bóbr $2$ musi być monitorowany przez cały czas.

W drugim przypadku testowym osiągnięcie konfiguracji końcowej nie jest możliwe.

W trzecim przypadku testowym nie trzeba wykonywać żadnych operacji.