L. [COCI 2006/2007 #3] BICIKLI

Type: RemoteJudge

1000ms

128MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

一场自行车比赛将要在一个遥远的地方上举行。

这个地方有 $n$ 个城镇，从 $1\sim n$ 编号，其中有 $m$ 条单向道路连接它们。比赛将在 $1$ 号城镇开始并在 $2$ 号城镇结束。

主办方想知道，一共有多少条不同的路线？

输入第一行为两个整数 $n,m$ ，意义如题目描述所示。

接下来的 $m$ 行，每行两个整数 $a,b$ ，描述一条从 $a$ 到 $b$ 的道路。

两个城镇间可以有多条道路。

输出不同的路线的数量。

如果有无数条不同的路线，则输出 inf。

否则输出路线数对 $10^9$ 取模的结果。

inf

对于 $100\%$ 的数据， $1\le n\leq 5\times 10 ^ 4$ ， $1\leq m\le 10^5$ 。

题目译自 COCI2006-2007 CONTEST #3 T5 BICIKLI

感谢

https://www.luogu.com.cn/user/45475

翻译。