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

There are $N$ airports in a certain country, and the Jag Airlines Group operates $M$ flights connecting these airports. To reduce the number of airplanes required, they choose to rearrange the order of flights. In each flight, an airplane departs from one airport and arrives at another, and each flight must be operated by exactly one airplane. We denote by $a \rightarrow b$ a flight that departs from airport $a$ and arrives at airport $b$. An airplane can operate a flight $x \rightarrow y$ only if one of the following holds: - The airplane was initially placed at airport $x$ and has not yet operated any flight. - The destination of its most recent operation was airport $x$. For example, suppose there are three flights: $a \rightarrow b$, $c \rightarrow a$, and $b \rightarrow d$. If they are ordered as $c \rightarrow a$, $b \rightarrow d$, and $a \rightarrow b$, then $c \rightarrow a$ and $a \rightarrow b$ can be operated by the same airplane, so the three flights can be operated by two airplanes. You may reorder the $M$ flights arbitrarily and choose the initial placements of the airplanes arbitrarily. What is the minimum number of airplanes required to operate all the flights?

The input consists of multiple test cases. The first line contains an integer $T$ ($1 \leq T \leq 1000$), representing the number of test cases. $T$ test cases follow. Each test case is given in the following format. $$\begin{aligned} & N \ M \\ & a_{1} \ b_{1} \\ & \vdots \\ & a_{M} \ b_{M} \end{aligned}$$ For each test case, the first line contains integers $N$ ($2 \leq N \leq 300\,000$) and $M$ ($1 \leq M \leq 300\,000$), representing the number of airports and the number of flights, respectively. The following $M$ lines each contain integers $a_i$ and $b_i$, satisfying $1 \leq a_i, b_i \leq N$ and $a_i \neq b_i$. Each line describes the $i$-th flight $a_i \rightarrow b_i$. Additionally, the sum of $N$ over all test cases does not exceed $300\,000$, and the sum of $M$ over all test cases does not exceed $300\,000$.

For each of the $T$ test cases, output the minimum number of airplanes required, one per line.