問題文

N 頂点 M 辺の単純有向グラフ G があります。 頂点には 1 から N までの番号が付けられていて、i 本目の辺は頂点 u_i から頂点 v_i への有向辺です。

あなたは以下の操作を何回でも行うことができます。

• G の入次数 0 の頂点 v を選び、v を端点とするすべての辺の向きを反転する。

操作を行うことができる最大の回数を求めてください。ただし、操作を無限に続けることができる場合、その旨を報告してください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \leq T \leq 5 \times 10^4
• 2 \leq N \leq 10^5
• 1 \leq M \leq \min(N(N-1), 2 \times 10^5)
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• (u_i,v_i) \neq (u_j,v_j) \ (i \neq j)
• すべてのテストケースに対する N の総和は 10^5 以下
• すべてのテストケースに対する M の総和は 2 \times 10^5 以下
• 入力される数値はすべて整数

入力例 1

4
5 6
1 3
2 4
2 5
3 4
4 1
5 1
2 1
1 2
3 2
1 2
2 1
6 6
1 2
2 3
3 4
4 5
5 6
6 1

出力例 1

2
-1
-1
0

1 つ目のテストケースについて、以下のように操作することで、2 回操作を行うことができます。

• 頂点 2 に対して操作を行う。2, 3 番目の辺の向きが反転する。
• 頂点 5 に対して操作を行う。3, 6 番目の辺の向きが反転する。

3 回以上操作を行うことはできないので、2 を出力します。

2 つ目のテストケースについて、頂点 1 、頂点 2 に対して交互に操作を行うことで、無限に操作を続けることができます。

3 つ目のテストケースについて、頂点 3 に対して何回でも操作を行うことができます。

4 つ目のテストケースについて、1 回も操作を行うことができません。