V. [COCI 2006/2007 #3] BICIKLI

远端评测题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

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

这个地方有 $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

翻译。