MITIT(Monitored Industrious Timbercrafters Infrastructure Technology)는 $1, \dots, N$ 번호가 매겨진 $N$마리의 비버로 구성되어 있습니다. $M$개의 비버 쌍 $(u_i, v_i)$가 존재하며, 처음에 비버 $u_i$는 비버 $v_i$를 감시합니다. 모든 비버는 항상 적어도 한 마리의 다른 비버에게 감시받아야 합니다.

MITIT의 관리자인 Busy Beaver는 이러한 감시 관계를 재구성하고자 합니다. 한 번의 연산으로 비버 $u$가 비버 $v$를 감시하고 있는 쌍 $(u, v)$를 선택하여, 비버 $v$가 비버 $u$를 감시하도록 바꿀 수 있습니다. 단, 모든 비버가 항상 적어도 한 마리의 다른 비버에게 감시받아야 한다는 조건을 만족해야 합니다.

Busy Beaver가 원하는 최종 구성은 길이 $M$인 문자열 $d$로 설명할 수 있습니다. $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$)이 주어집니다.

다음 $M$개의 줄 중 $i$번째 줄에는 두 정수 $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$이 주어지며, 모든 $1 \le i \le M$에 대해 $d_i \in \{0, 1\}$입니다.

초기 구성과 최종 구성 모두에서 각 비버는 적어도 한 마리의 다른 비버에게 감시받음이 보장됩니다.

모든 테스트 케이스에 대한 $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$는 항상 가능한 최소 연산 횟수여야 합니다. 그렇지 않은 경우, 모든 테스트 케이스에 걸친 $K$의 합이 $10^6$을 넘지 않는 유효한 연산 순서를 올바르게 출력하면 각 서브태스크 점수의 $50\%$를 받습니다.

• ($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$는 항상 감시받아야 하므로 연산을 반대 순서로 수행하는 것은 허용되지 않음에 유의하십시오.

두 번째 테스트 케이스에서는 최종 구성에 도달하는 것이 불가능합니다.

세 번째 테스트 케이스에서는 수행해야 할 연산이 없습니다.