Two Longest Paths#2627
Tekuhp is a tourist city. The city contains intersections, connected by one-way roads. Each one-way road leads from one intersection to another. There may be multiple roads between a pair of intersections. To make the city unusual, the roads are constructed so that it is not possible to start at any intersection, travel along the roads, and return to the starting intersection. (It remains a strange secret how the residents of Tekuhp return home from work every day.)
Two groups of tourists are visiting the city. They wish to travel along the roads from one intersection to another. However, they do not want to meet each other. Therefore, they require two paths P_1 and P_2; for each P_i (1 \leq i \leq 2), the path starts at some intersection s_i and ends at intersection t_i, such that the two paths do not share any intersection, including their starting and ending intersections. However, it is possible that P_i consists of only one node, i.e., s_i = t_i.
The tourists also want to visit as many places as possible. As a good organizer, your task is to maximize the total number of intersections included in both paths.
The first line contains a single integer (1 \leq T \leq 10) — the number of test cases. Then test cases follow.
Each test case starts with integers and (1 \leq N \leq 300; 1 \leq M \leq 3000), the number of intersections and roads. Intersections are numbered from to . Each of the next lines describes a road, containing two integers and — a one-way road from intersection to intersection .
The output must contain lines. For each test case, output a single integer — the maximum number of intersections covered by both paths.
Example 1