Jeju Island Tour

Many tourists visit Jeju Island. The island has $N$ intersections and $M$ one way roads. Each road runs from one intersection to another, and several roads may connect the same pair of intersections.

The roads on Jeju Island are laid out in a very strange shape. Whichever intersection you start from, you can never follow the roads and get back to the intersection you started at. (So how do the people who live there get to work?)

Two groups are planning a trip around the island. Each group starts at one intersection and travels along the roads. The two groups get along badly, so they must not pass through the same intersection. You have to pick two routes $P_1$ and $P_2$, where $P_i$ ($1 \le i \le 2$) starts at intersection $s_i$ and finishes at intersection $t_i$, and the two routes must not share a single intersection. The starting and finishing points must not overlap either. A route $P_i$ containing only one intersection is allowed ($s_i = t_i$).

Write a program that maximizes the total number of intersections on the two routes.

The first line contains the number of test cases $T$ ($1 \le T \le 10$).

The first line of each test case contains the number of intersections $N$ and the number of roads $M$ ($1 \le N \le 300$, $1 \le M \le 3000$). The intersections are numbered from $1$ to $N$. Each of the next $M$ lines contains two integers $A$ and $B$ describing one road, meaning there is a one way road from intersection $A$ to intersection $B$.

For each test case, print on its own line the largest possible total number of intersections on two routes that satisfy the conditions.