City Round Trips 2

There are N cities and P bidirectional roads. You want to travel repeatedly between city 1 and city 2.

Across all trips, no city except cities 1 and 2 may be visited more than once. One trip is a path from city 1 to city 2, or from city 2 to city 1, and it must pass through at least one intermediate city.

The input never contains a road directly connecting city 1 and city 2. Cities are numbered from 1 to N. Find the maximum number of trips that can be made while satisfying these conditions.

The first line contains two integers N and P.

• 3 <= N <= 400
• 1 <= P <= 10,000

Each of the next P lines contains the numbers of two different cities connected by one road.

Print the maximum number of trips possible between city 1 and city 2 while satisfying the conditions.