Monitored Industrious Timbercrafters Infrastructure Technology (MITIT) は、$1, \dots, N$ の番号が付けられた $N$ 匹のビーバーで構成されています。$M$ 組のビーバーのペア $(u_i, v_i)$ があり、初期状態ではビーバー $u_i$ がビーバー $v_i$ を監視しています。各ビーバーは少なくとも他の 1 匹のビーバーによって監視されています。

MITIT のマネージャーである Busy Beaver は、これらの監視関係を再構成したいと考えています。1 回の操作で、現在ビーバー $u$ がビーバー $v$ を監視しているペア $(u, v)$ を選び、代わりにビーバー $v$ がビーバー $u$ を監視するように変更できます。ただし、常にすべてのビーバーが少なくとも他の 1 匹のビーバーによって監視されている状態を維持しなければなりません。

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$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、2 つの整数 $N$ と $M$ ($3 \le N \le M \le 10^5$) が含まれます。

続く $M$ 行の各行には、2 つの整数 $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\}$ です。

初期状態および最終状態のいずれにおいても、各ビーバーが少なくとも他の 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$ は常に監視されている必要があるため、操作を逆の順序で行うことは許容されないことに注意してください。

2 番目のテストケースでは、最終構成に到達することは不可能です。

3 番目のテストケースでは、操作を行う必要はありません。