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`。

### 样例解释 1 对于第 $1$ 个测试用例，可以按如下方式操作，从而执行 $2$ 次操作。 - 对顶点 $2$ 执行操作。第 $2$、$3$ 条边的方向被反转。 - 对顶点 $5$ 执行操作。第 $3$、$6$ 条边的方向被反转。 无法执行 $3$ 次以上操作，因此输出 $2$。 对于第 $2$ 个测试用例，通过交替对顶点 $1$、顶点 $2$ 执行操作，可以无限继续操作。 对于第 $3$ 个测试用例，可以对顶点 $3$ 任意多次执行操作。 对于第 $4$ 个测试用例，一次操作也无法执行。 ### 约束 - $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$ - 输入中的所有数值均为整数 由 DeepSeek V4.1 Flash 翻译。