Informatica Online Judge

  경곽길 [1675 / 068B]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 6   Total Tried : 56


The Champion of this Problem (C++) : dotorya - 0ms / 2679byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

경곽시는 관광객 유치를 위해 북한산 둘레길이나 제주도 올레길과 같이 마을과 마을을 연결하는 경곽길을 만들고자 한다.

마을은 $1$개이상의 길을 포함하고 있으며, 갔던 길은 또 갈 수 있다.

그러나, 경곽길은 안전문제로 일방통행길로 만들어야 하고, 재정문제로 관리사무소를 $1$번 마을과 $2$번 마을에만 설치할 수 밖에 없다.

$N$개의 마을과 마을과 마을을 연결하는 $M$개의 길이 있을 때, $1$번 마을의 관리사무소를 시작으로 $2$번 마을의 관리사무소까지 갈 수 있도록 만들 수 있는 경곽길은 모두 몇 개인가?

Input

첫 번째 줄에는 마을 개수 $N$와 길 $M$을 입력한다.
두 번째 줄부터는 $A$마을에서 $B$마을로 향하는 길을 입력한다.

[입력값의 정의역]
$1 <= N <= 10,000$
$1 <= M <= 100,000$

Output

$1$번 마을의 관리사무소에서 $2$번 마을의 관리사무소까지 갈 수 있도록 만들 수 있는 경곽길 경우의 수를 입력한다.

만약 경로의 수가 9자리를 넘어가면 마지막 9자리를 출력하며, 결과가 무한대의 경우가 나오면 “OH NO”를 출력한다.

IO Example

입력
6 7
3 4
1 3
3 2
4 2
6 5
1 4
5 6


출력
3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]