Инфраструктура мониторинга трудолюбивых бобров (MITIT) состоит из $N$ бобров, пронумерованных от $1$ до $N$. Существует $M$ пар бобров $(u_i, v_i)$, где изначально бобр $u_i$ отвечает за мониторинг бобра $v_i$. Каждый бобр находится под мониторингом как минимум одного другого бобра.

Занятой Бобр, менеджер MITIT, хочет изменить эти отношения мониторинга. За одну операцию он может выбрать пару $(u, v)$, где бобр $u$ в данный момент следит за бобром $v$, и сделать так, чтобы бобр $v$ следил за бобром $u$. Однако он должен гарантировать, что каждый бобр всегда находится под мониторингом как минимум одного другого бобра.

Желаемая конечная конфигурация Занятого Бобра описывается строкой $d$ длины $M$, где $d_i = 0$, если бобр $u_i$ следит за бобром $v_i$ в конце, и $d_i = 1$, если бобр $v_i$ следит за бобром $u_i$ в конце. Найдите кратчайшую последовательность операций, необходимую для достижения этой конфигурации, или сообщите, что это невозможно.

Входные данные

Каждый тест содержит несколько тестовых случаев. Первая строка содержит количество тестовых случаев $T$ ($1 \le T \le 10^4$). Далее следует описание тестовых случаев.

Первая строка каждого тестового случая содержит два целых числа $N$ и $M$ ($3 \le N \le M \le 10^5$).

$i$-я из следующих $M$ строк содержит два целых числа $u_i$ и $v_i$ ($1 \le u_i, v_i \le N, u_i \ne v_i$). Не существует таких $1 \le i < j \le M$, что $(u_i, v_i) = (u_j, v_j)$ или $(u_i, v_i) = (v_j, u_j)$.

Следующая строка содержит строку $d_1 \dots d_M$, где $d_i \in \{0, 1\}$ для всех $1 \le i \le M$.

Гарантируется, что как в начальной, так и в конечной конфигурации каждый бобр находится под мониторингом как минимум одного другого бобра.

Гарантируется, что сумма $N$ по всем тестовым случаям не превышает $10^5$.

Гарантируется, что сумма $M$ по всем тестовым случаям не превышает $10^5$.

Выходные данные

Для каждого тестового случая, если задача невыполнима, выведите единственное число $-1$.

В противном случае сначала выведите целое число $K$ — количество выполненных операций. На следующей строке выведите $K$ целых чисел $a_1, \dots, a_K$ ($1 \le a_i \le M$), означающих, что ваше решение выполняет операции над парами $(u_{a_i}, v_{a_i})$ в указанном порядке.

Подзадачи

Для получения полного балла $K$ всегда должно быть минимально возможным количеством операций. В противном случае вы получите $50\%$ баллов за каждую подзадачу, если корректно выведете любую допустимую последовательность операций, при которой сумма $K$ по всем тестовым случаям не превышает $10^6$.

• ($50$ баллов) $M \le 300$.
• ($50$ баллов) Дополнительных ограничений нет.

Примеры

Пример 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

Выходные данные 1

2
2 1 
-1
0

Примечание

Операции в первом тестовом случае показаны ниже. Обратите внимание, что выполнение операций в обратном порядке недопустимо, так как бобр $2$ должен находиться под мониторингом в любой момент времени.

Во втором тестовом случае достичь конечной конфигурации невозможно.

В третьем тестовом случае операции выполнять не требуется.