도시 왕복하기 2

N개의 도시와 P개의 양방향 도로가 있다. 1번 도시와 2번 도시 사이를 반복해서 이동하려고 한다.

여러 번 이동하는 동안 1번 도시와 2번 도시를 제외한 어떤 도시도 두 번 이상 방문하면 안 된다. 한 번의 이동은 1번 도시에서 2번 도시로 가거나 2번 도시에서 1번 도시로 가는 경로이며, 반드시 하나 이상의 중간 도시를 지나야 한다.

입력에는 1번 도시와 2번 도시를 직접 잇는 도로가 없다. 도시 번호는 1번부터 N번까지이다. 조건을 지키며 이동할 수 있는 최대 횟수를 구하라.

첫째 줄에 두 정수 N과 P가 주어진다.

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

다음 P개의 줄에는 각 도로가 연결하는 서로 다른 두 도시의 번호가 주어진다.

조건을 지키며 1번 도시와 2번 도시 사이를 이동할 수 있는 최대 횟수를 출력한다.