P15787 [JAG 2025 Summer Camp #3] Flight Planning 2

某个国家有 $N$ 个机场，Jag 航空集团运营着 $M$ 个连接这些机场的航班。为了减少所需的飞机数量，他们决定重新安排航班的执行顺序。 在每个航班中，一架飞机从一个机场起飞并抵达另一个机场，且每个航班必须由恰好一架飞机执飞。我们用 $a \rightarrow b$ 表示一个从机场 $a$ 起飞并抵达机场 $b$ 的航班。 一架飞机能够执飞航班 $x \rightarrow y$，当且仅当满足以下条件之一： - 该飞机最初被放置在机场 $x$，且尚未执飞过任何航班。 - 该飞机最近一次执飞的航班的目的地是机场 $x$。 例如，假设有三个航班：$a \rightarrow b$、$c \rightarrow a$ 和 $b \rightarrow d$。如果将它们按顺序安排为 $c \rightarrow a$、$b \rightarrow d$、$a \rightarrow b$，那么 $c \rightarrow a$ 和 $a \rightarrow b$ 可以由同一架飞机执飞，因此这三个航班可以由两架飞机完成。 你可以任意重新排列这 $M$ 个航班的顺序，并任意选择飞机的初始放置位置。请问，要执飞所有航班，最少需要多少架飞机？

输入包含多个测试用例。 第一行包含一个整数 $T$（$1 \leq T \leq 1000$），表示测试用例的数量。 接下来是 $T$ 个测试用例。每个测试用例的格式如下。 $$\begin{aligned} & N \ M \\ & a_{1} \ b_{1} \\ & \vdots \\ & a_{M} \ b_{M} \end{aligned}$$ 对于每个测试用例，第一行包含两个整数 $N$（$2 \leq N \leq 300\,000$）和 $M$（$1 \leq M \leq 300\,000$），分别表示机场的数量和航班的数量。 接下来的 $M$ 行，每行包含两个整数 $a_i$ 和 $b_i$，满足 $1 \leq a_i, b_i \leq N$ 且 $a_i \neq b_i$。每行描述第 $i$ 个航班 $a_i \rightarrow b_i$。 此外，所有测试用例的 $N$ 的总和不超过 $300\,000$，所有测试用例的 $M$ 的总和不超过 $300\,000$。

对于 $T$ 个测试用例中的每一个，输出一行，表示所需的最少飞机数量。

翻译由 DeepSeek V3.2 完成