監控勤奮木工基礎設施技術（MITIT）由 $N$ 隻編號為 $1, \dots, N$ 的海狸組成。共有 $M$ 對海狸 $(u_i, v_i)$，最初海狸 $u_i$ 負責監控海狸 $v_i$。每隻海狸都至少被另一隻海狸監控。

MITIT 的經理「忙碌海狸」想要重新配置這些監控關係。在一次操作中，他可以選擇一對 $(u, v)$，其中海狸 $u$ 目前正在監控海狸 $v$，並將其改為由海狸 $v$ 監控海狸 $u$。然而，他必須確保在任何時候，每隻海狸都至少被另一隻海狸監控。

忙碌海狸期望的最終配置可以用一個長度為 $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$ 必須始終受到監控。

在第二個測試案例中，無法達到最終配置。

在第三個測試案例中，不需要執行任何操作。