Traveling Cows
Time limit1sMemory limit1024 MB
Find the maximum number of paths from field 1 to field 2 that share no non-barn field, where each path passes through at least one non-barn field.
Problem
N (3 ≤ N ≤ 400) fields numbered 1 to N are connected by P (1 ≤ P ≤ 10,000) bidirectional paths. Fields 1 and 2 contain barns. Bessie wants to travel back and forth between these two barns along the paths as many times as possible. She does not want to visit any field more than once across all her trips, except for the fields containing barns. Each trip between the two barns must pass through at least one non-barn field. The input contains neither "1 2" nor "2 1".
What is the maximum number of trips Bessie can make?
Input
The first line contains two integers N and P. Each of the next P lines contains two integers, the numbers of two fields connected by a path.
Output
Print a single integer, the maximum number of trips Bessie can make.