프로그램 명: coci_bicikli
제한시간: 1 초
[문제요약] 1 번 정점에서 2 번 정점으로 끝나는 길의 종류를 구하는 문제. 무한하다면 inf 를 출력
입출력 예1 입출력 예2
A bicycle race is being organized in a land far, far away. There are N town in the land, numbered 1
through N. There are also M one-way roads between the towns. The race will start in town 1 and end
in town 2.
How many different ways can the route be set? Two routes are considered different if they do not use
the exact same roads.
입력
The first line of input contains two integers N and M (1 ≤ N ≤ 10 000, 1 ≤ M ≤ 100 000), the number
of towns and roads.
Each of the next M lines contains two different integers A and B, representing a road between towns A
and B.
Towns may be connected by more than one road.
출력
Output the number of distinct routes that can be set on a single line. If that number has more than nine
digits, output only the last nine digits of the number. If there are infinitely many routes, output "inf".
입출력 예
입력
6 7
1 3
1 4
3 2
4 2
5 6
6 5
3 4
출력
3
입력
6 8
1 3
1 4
3 2
4 2
5 6
6 5
3 4
4 3
출력
inf
입력
31 60
1 3
1 3
3 4
3 4
4 5
4 5
5 6
5 6
6 7
6 7
…
…
…
28 29
28 29
29 30
29 30
30 31
30 31
31 2
31 2
출력
073741824
출처:coci/2006-2007/contest3 5
[질/답]
[제출 현황]
[푼 후(0)]