P7737 [NOI2021] 庆典

C 国是一个繁荣昌盛的国家，它由 $n$ 座城市和 $m$ 条有向道路组成，城市从 $1$ 到 $n$ 编号。如果从 $x$ 号城市出发，经过若干条道路后能到达 $y$ 号城市，那么我们称 $x$ 号城市可到达 $y$ 号城市，记作 $x\Rightarrow y$。C 国的道路有一个特点：对于三座城市 $x$，$y$，$z$，若 $x\Rightarrow z$ 且 $y\Rightarrow z$，那么有 $x\Rightarrow y$ 或 $y\Rightarrow x$。 再过一个月就是 C 国成立的千年纪念日，所以 C 国的人民正在筹备盛大的游行庆典。目前 C 国得知接下来会有 $q$ 次游行计划，第 $i$ 次游行希望从城市 $s_i$ 出发，经过若干个城市后，在城市 $t_i$ 结束，且在游行过程中，**一个城市可以被经过多次**。为了增加游行的乐趣，每次游行还会**临时**修建出 $k$（$0 \le k \le 2$）条有向道路专门供本次游行使用，即其它游行计划不能通过本次游行修建的道路。 现在 C 国想知道，每次游行计划可能会**经过多少座城市**。 注意：临时修建出的道路**可以不满足 C 国道路原有的特点**。

无

无

**【样例解释 #1】** 第 $1$ 次计划，起点为 $1$ 号点，终点为 $4$ 号点，临时修建道路为 $5\rightarrow1$，最终可能经过的城市编号为 $\{1,2,4,5\}$。 第 $2$ 次计划，起点为 $2$ 号点，终点为 $3$ 号点，临时修建道路为 $5\rightarrow3$，最终可能经过的城市编号为 $\{2,3,4,5\}$。 第 $3$ 次计划，起点为 $1$ 号点，终点为 $2$ 号点，临时修建道路为 $5\rightarrow2$，最终可能经过的城市编号为 $\{1,2,4,5\}$。 第 $4$ 次计划，起点为 $3$ 号点，终点为 $4$ 号点，临时修建道路为 $5\rightarrow1$，最终从 $3$ 号点出发无法到达 $4$ 号点。 **【样例 #2】** 见附件 `celebration/celebration2.in` 与 `celebration/celebration2.ans`。 该样例约束与测试点 $5 \sim 7$ 一致。 **【样例 #3】** 见附件 `celebration/celebration3.in` 与 `celebration/celebration3.ans`。 该样例约束与测试点 $10 \sim 11$ 一致。 **【样例 #4】** 见附件 `celebration/celebration4.in` 与 `celebration/celebration4.ans`。 该样例约束与测试点 $15 \sim 16$ 一致。 **【样例 #5】** 见附件 `celebration/celebration5.in` 与 `celebration/celebration5.ans`。 该样例约束与测试点 $20 \sim 25$ 一致。 **【数据范围】** 对于所有测试点，$1 \le n,q \le 3 \times {10}^5$，$n - 1 \le m \le 6 \times {10}^5$，$0 \le k \le 2$。 | 测试点编号 | $n, q \le$ | $k$ | 特殊性质 | |:-:|:-:|:-:|:-:| | $1 \sim 4$ | $5$ | $= 0$ | 无 | | $5 \sim 7$ | $1000$ | $\le 2$ | 无 | | $8 \sim 9$ | $3 \times {10}^5$ | $= 0$ | $m = n - 1$ | | $10 \sim 11$ | $3 \times {10}^5$ | $= 1$ | $m = n - 1$ | | $12 \sim 14$ | $3 \times {10}^5$ | $= 2$ | $m = n - 1$ | | $15 \sim 16$ | $3 \times {10}^5$ | $= 0$ | 无 | | $17 \sim 19$ | $3 \times {10}^5$ | $= 1$ | 无 | | $20 \sim 25$ | $3 \times {10}^5$ | $= 2$ | 无 |