J. Traveling Alien Masud
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Masud found a map of the earth and is planning on visiting it. There are a total of $$$n$$$ cities. Each city belongs to only one country. Two cities are connected via one-way roads. Two cities are considered to be in the same country if it is possible to reach the second city (directly or indirectly) starting from the first one and also reach the first city starting from the second one. Otherwise, the cities are of different countries.

Now Masud is very busy and can only prepare the necessary documents to travel to at most two different countries. But he wants to visit as many cities as possible. Can you help him find the maximum number of cities he can visit by traveling to at most two countries?

Note that the two chosen countries do not necessarily need to be reachable from each other.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 25$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$\left(1 \leq n \leq 10^5;\ 1 \leq m \leq 10^5\right)$$$ — the number of cities and the number of one-way roads connecting them.

The following $$$m$$$ lines of the test case contain two integers $$$u$$$ and $$$v$$$ $$$(1 \le u, v \le n;\ u \neq v)$$$ denoting a directional road from city $$$u$$$ to city $$$v$$$.

Output

For each test case, output the maximum number of cities Masud can visit during his visit to earth on a separate line.

Example
Input
1
7 8
1 2
2 3
3 4
4 1
5 6
6 7
7 5
1 5
Output
7