E. Monitoring Beavers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Monitored Industrious Timbercrafters Infrastructure Technology (MITIT) is composed of $$$N$$$ beavers numbered $$$1,\dots,N$$$. There are $$$M$$$ pairs of beavers $$$(u_i,v_i)$$$, where initially, beaver $$$u_i$$$ is responsible for monitoring beaver $$$v_i$$$. Each beaver is monitored by at least one other beaver.

Busy Beaver, the manager of MITIT, would like to reconfigure these monitoring relations. In one operation, he can take a pair $$$(u,v)$$$ where beaver $$$u$$$ is currently monitoring beaver $$$v$$$ and make beaver $$$v$$$ monitor beaver $$$u$$$ instead. However, he must ensure that every beaver is monitored by at least one other beaver at all times.

Busy Beaver's desired final configuration can be described by a string $$$d$$$ of length $$$M$$$, where $$$d_i = 0$$$ if beaver $$$u_i$$$ monitors beaver $$$v_i$$$ at the end and $$$d_i = 1$$$ if beaver $$$v_i$$$ monitors beaver $$$u_i$$$ at the end. Find a shortest sequence of operations necessary to reach this final configuration, or report that it is impossible.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$N$$$ and $$$M$$$ ($$$3 \le N \le M \le 10^5$$$).

The $$$i$$$th of the next $$$M$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le N, u_i \ne v_i$$$). There does not exist $$$1 \le i \lt j \le M$$$ where $$$(u_i,v_i) = (u_j,v_j)$$$ or $$$(u_i,v_i) = (v_j,u_j)$$$.

The next line contains a string $$$d_1 \dots d_M$$$, where $$$d_i \in \{0,1\}$$$ for all $$$1 \le i \le M$$$.

It is guaranteed that in both the initial and final configurations, each beaver is monitored by at least one other beaver.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$10^5$$$.

It is guaranteed that the sum of $$$M$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, if the task is impossible, output a single integer $$$-1$$$.

Otherwise, first output an integer $$$K$$$, the number of operations used. On the next line, output $$$K$$$ integers $$$a_1,\dots,a_K$$$ ($$$1 \le a_i \le M$$$), representing that your solution performs operations on $$$(u_{a_i},v_{a_i})$$$ in order.

Scoring

For full points, $$$K$$$ should always be the minimum possible number of operations. Otherwise, you will receive $$$50\%$$$ of the points for each subtask if you correctly output any valid sequence of operations where the sum of $$$K$$$ across all test cases does not exceed $$$10^6$$$.

  • ($$$50$$$ points) $$$M \le 300$$$.
  • ($$$50$$$ points) No additional constraints.
Example
Input
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
Output
2
2 1 
-1
0
Note

The operations in the first test case are shown below. Note that performing the operations in the opposite order is not acceptable because beaver $$$2$$$ must be monitored at all times.

In the second test case, it is not possible to reach the final configuration.

In the third test case, no operations need to be performed.