사업 확장

성공한 벤처 회사 "봉씨"의 대표 연종이는 사업을 미국으로 확장하기로 했다.

봉씨는 LA에 있는 투자자들을 만나기 위해 미국으로 출발했다. 그러나 비행기에서 내리고 보니 도착지는 LA가 아니라 뉴욕이었다. 연종이의 비서는 아는 미국 도시가 뉴욕뿐이라서, 사장의 항공편도 당연히 뉴욕행으로 예약한 것이다.

연종이는 LA까지 가는 비용을 최대한 줄이기 위해 비행기 대신 차를 빌려 이동하려고 한다.

미국에는 N개의 도시가 있고, 각 도시는 1번부터 N번까지 번호가 매겨져 있다. 도로는 M개이며, 각 도로는 두 도시를 한 방향으로만 연결한다.

뉴욕은 1번 도시이고, LA는 2번 도시이다.

연종이의 회사는 매우 높은 가치를 지닌 회사라서, 연종이가 방문하는 모든 도시에 경호원을 고용해야 한다. 한 도시에서 경호원을 한 번 고용하면 그 도시를 여러 번 방문하더라도 다시 고용할 필요는 없다.

연종이는 1번 도시에서 출발해 2번 도시를 방문한 뒤 다시 1번 도시로 돌아오려고 한다. 이때 고용해야 하는 경호원 수의 최솟값을 구하라.

첫째 줄에 도시의 수 N과 도로의 수 M이 주어진다. (2 <= N <= 100, 2 <= M <= 200)

다음 M개의 줄에는 서로 다른 두 정수 A와 B가 주어진다. (1 <= A, B <= N) 이는 A번 도시에서 B번 도시로 가는 도로가 있음을 뜻한다.

같은 도로가 두 번 이상 주어지지는 않지만, 반대 방향 도로가 함께 주어질 수는 있다.

연종이가 1번 도시에서 2번 도시로 갔다가 다시 1번 도시로 돌아오는 동안 고용해야 하는 경호원 수의 최솟값을 첫째 줄에 출력한다.

입력은 항상 가능한 경로가 존재하는 경우만 주어진다.

첫 번째 공개 테스트에서는 1 -> 3 -> 4 -> 2 -> 6 -> 3 -> 4 -> 5 -> 1 순서로 이동할 수 있다. 이때 방문한 도시는 1, 2, 3, 4, 5, 6으로 총 6개이다.