Traveling Cows

N (3 ≤ N ≤ 400) fields numbered 1..N are connected by P (1 ≤ P ≤ 10,000) bidirectional pathways. Fields 1 and 2 contain barns. Bessie wants to travel on the paths back and forth between these two barns as many times as possible -- however, she doesn't want to visit any field more than one time in all her trips (except for the fields containing barns). Bessie must visit at least one non-barn field when traveling between the two barns; the input set contains neither "1 2" nor "2 1".

What is the maximum number of trips Bessie can make?

• Line 1: Two integers: N and P
• Lines 2..P+1: Two integers that represent two fields connected by a path

A single integer that is the maximum number of trips that Bessie can make.