레이팅 미적용설명
머나먼 나라에서 자전거 경주가 열린다. 이 나라에는 \(1\)부터 \(N\)까지 번호가 붙은 \(N\)개의 마을이 있다. 마을 사이에는 \(M\)개의 일방통행 도로도 있다. 경주는 마을 \(1\)에서 시작해 마을 \(2\)에서 끝난다.
경주로를 정하는 방법은 몇 가지인가? 두 경주로가 정확히 같은 도로들을 사용하지 않으면 서로 다른 것으로 본다.
제약
입력 형식
입력의 첫째 줄에 두 정수 \(N\)과 \(M\) (\(1 \le N, M \le 10000\))이 주어진다. 마을과 도로의 개수이다.
다음 \(M\)개의 줄에는 서로 다른 두 정수 \(A\)와 \(B\)가 주어진다. 마을 \(A\)에서 마을 \(B\)로 가는 도로를 나타낸다.
두 마을이 두 개 이상의 도로로 연결되어 있을 수도 있다.
출력 형식
정할 수 있는 서로 다른 경주로의 개수를 한 줄에 출력한다. 그 수가 아홉 자리를 넘으면 마지막 아홉 자리만 출력한다. 경주로가 무한히 많으면 inf를 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 70점 |
예제 1
입력
6 7
1 3
1 4
3 2
4 2
5 6
6 5
3 4출력
3예제 2
입력
6 8
1 3
1 4
3 2
4 2
5 6
6 5
3 4
4 3출력
inf예제 3
입력
31 60
1 3
1 3
3 4
3 4
4 5
4 5
5 6
5 6
6 7
6 7
7 8
7 8
8 9
8 9
9 10
9 10
10 11
10 11
11 12
11 12
12 13
12 13
13 14
13 14
14 15
14 15
15 16
15 16
16 17
16 17
17 18
17 18
18 19
18 19
19 20
19 20
20 21
20 21
21 22
21 22
22 23
22 23
23 24
23 24
24 25
24 25
25 26
25 26
26 27
26 27
27 28
27 28
28 29
28 29
29 30
29 30
30 31
30 31
31 2
31 2출력
073741824문제 정보
태그