자전거 경주 경로 세기

1번부터 N번까지 번호가 붙은 N개의 마을이 있고, 마을 사이에는 M개의 일방통행 도로가 있다. 이 나라에서는 자전거 경주를 열려고 한다. 경주는 반드시 1번 마을에서 시작해서 2번 마을에서 끝나야 한다.

가능한 경주 경로의 수를 구하라. 같은 두 마을 사이에 여러 도로가 있을 수 있으며, 서로 다른 도로를 사용하면 서로 다른 경로로 센다. 어떤 순환 구조 때문에 1번 마을에서 2번 마을까지 갈 수 있는 경로가 무한히 많아질 수도 있다.

첫째 줄에 마을의 수 N과 도로의 수 M이 주어진다. (2 <= N <= 10,000, 1 <= M <= 100,000)

다음 M개 줄에는 도로의 정보를 나타내는 두 정수 A와 B가 주어진다. 이는 A번 마을에서 B번 마을로 가는 일방통행 도로를 의미한다.

같은 두 마을 사이에 도로가 하나 이상 존재할 수 있다.

첫째 줄에 가능한 자전거 경주 경로의 수를 출력한다. 경로의 수가 9자리를 넘어가면 마지막 9자리만 출력한다. 이때 앞자리가 0이면 9자리가 되도록 0을 포함해서 출력한다.

경로의 수가 무한대이면 inf를 출력한다.