Problem F
Two Longest Paths
Input: Standard Input
Output: Standard Output
Tekuhp is a tourist city. There are N
intersections in the city, connected with M one-way roads. Each one-way
road connects from some intersection to another. There maybe many roads that
connect a pair of intersections. To make the city very amazing, the roads are
constructed so that it is not possible to start at some
intersection, travel along the roads, and return to the starting intersection.
(It remains a strange secret how people of Tekuhp return home from work each
day.)
There are two groups of tourists planning to
visit the city. They want to travel along the roads from some intersection to
another. However, both groups do not want to run into each other. So they want
two paths P1 and P2, each Pi
, for 1 <= i <= 2, starts at some intersection si
and ends at intersection ti, such that both paths share no
intersections, including the starting and the ending intersections.
However, it is possible that a path Pi may contain only one
node, i. e., si = ti.
Tourists also want to visit many places.
Since you are a good planner, you want to maximize the total number of intersections
in both path.
Input
First line of the
input contains an integer T (1 <= T <= 10), the number of test cases.
After that T test cases follow.
Each test case
starts with integers N and M (1 <= N <= 300; 1 <=
M <= 3,000), where N denotes the number of intersections and M
denotes the number of roads. The intersections are numbered from 1 to N.
After that M lines, describing road connection, follow. Each line
contains two integers A and B denoting that there is a one-way
road from intersection A to intersection B.
Output
The output must contain T lines, each
line for each test case. For each test case, the output contains an integer L
denoting the maximum number of intersections in two non-intersecting paths.
|
Sample Input |
Output for Sample Input |
|
3 3 2 1 2 2 3 8 9 1 2 2 3 3 4 5 6 6 7 7 8 2 6 6 3 3 7 4 2 1 2 3 4 |
3 8 4 |
Problemsetter: Jittat
Fakcharoenphol