AT_bogosortcontest_div1_g Source to Sink

$ N $ 頂点 $ M $ 辺の単純有向グラフ $ G $ があります。 頂点には $ 1 $ から $ N $ までの番号が付けられていて、 $ i $ 本目の辺は頂点 $ u_i $ から頂点 $ v_i $ への有向辺です。 あなたは以下の操作を何回でも行うことができます。 - $ G $ の入次数 $ 0 $ の頂点 $ v $ を選び、 $ v $ を端点とするすべての辺の向きを反転する。 操作を行うことができる最大の回数を求めてください。ただし、操作を無限に続けることができる場合、その旨を報告してください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_M $ $ v_M $

$ T $ 行出力せよ。 $ t $ 行目には $ t $ 個目のテストケースの答えを出力せよ。 各テストケースについて、操作を行うことができる最大の回数を出力せよ。ただし、操作を無限に続けることができる場合、`-1` を出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、以下のように操作することで、 $ 2 $ 回操作を行うことができます。 - 頂点 $ 2 $ に対して操作を行う。 $ 2 $ , $ 3 $ 番目の辺の向きが反転する。 - 頂点 $ 5 $ に対して操作を行う。 $ 3 $ , $ 6 $ 番目の辺の向きが反転する。 $ 3 $ 回以上操作を行うことはできないので、 $ 2 $ を出力します。 $ 2 $ つ目のテストケースについて、頂点 $ 1 $ 、頂点 $ 2 $ に対して交互に操作を行うことで、無限に操作を続けることができます。 $ 3 $ つ目のテストケースについて、頂点 $ 3 $ に対して何回でも操作を行うことができます。 $ 4 $ つ目のテストケースについて、 $ 1 $ 回も操作を行うことができません。 ### Constraints - $ 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 $ 以下 - 入力される数値はすべて整数