도시 왕복하기 1
시간 제한2초메모리 제한512 MB
N개의 도시와 P개의 단방향 도로가 주어지고 1번과 2번 도시를 잇는 도로는 없을 때, 도로를 공유하지 않는 1번에서 2번으로 가는 경로의 최대 개수를 구한다.
문제
N개의 도시가 P개의 단방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 즐긴다. 성실한 이석원은 1번 도시에서 2번 도시로 가는 서로 다른 경로를 최대한 많이 찾으려고 한다. 이때 한 경로에 포함된 길은 다른 경로에 포함되면 안 된다. 입력에는 1번 도시와 2번 도시를 연결하는 길이 없다. 도시의 번호는 1번부터 N번까지이다.
입력
첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 출발 도시와 도착 도시의 번호가 주어지며, 두 번호는 다르다.
출력
1번 도시에서 2번 도시로 가는 서로 다른 경로의 최대 개수를 출력한다.