MITIT（Monitored Industrious Timbercrafters Infrastructure Technology）由 $N$ 只海狸组成，编号为 $1, \dots, 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$ 必须在任何时刻都被监视。

在第二个测试用例中，无法达到最终配置。

在第三个测试用例中，不需要执行任何操作。