시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 199 28 27 21.774%

문제

1번부터 N번까지 번호가 매겨져 있는 N개의 마을과 마을을 연결하는 M개의 일방통항 도로로 이루어진 나라가 있다. 이 나라에서는 자전거 경주 대회를 개최하려고 한다. 경주는 1번 마을에서 시작해야 하고, 2번 마을에서 끝나야 한다.

자전거 경주를 개최할 수 있는 경로의 수는 총 몇 가지가 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 100,000)

다음 M개 줄에는 도로의 정보를 나타내는 A와 B가 주어진다. 이 정보는 A에서 B로 향하는 도로를 나타낸다.

마을은 하나 이상의 도로로 연결되어 있을 수도 있다.

출력

첫째 줄에 가능한 자전거 경주 대회 경로의 수를 출력한다. 수가 9자리를 넘어가는 경우에는 뒤의 9자리만 출력하면 된다. 만약, 경로의 수가 무한대인 경우에는 "inf"를 출력한다.

예제 입력

6 7
1 3
1 4
3 2
4 2
5 6
6 5
3 4

예제 출력

3

힌트