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

题目描述

自从有了立体交通，道路不再受平面的限制，可以不用有十字路口，就让两条道路互相穿越。

已知城市中共有 $n$ 个站点（编号 $1～n$)，其中共有 $m$ 条单向道路。现在公交公司计划开设一些单行线的公交线路，需要保证起始站 $s$ 向终点站 $t$ 有通路连接，并且同一组 $(s,t)$ 仅开设一条线路。

现在请问至多能够开设多少条线路?

注意:允许存在环线，即 $s=t$。且由于是单行线，$(s,t)$ 与 $(t,s)$ 视为不同线路。

输入格式

第一行：$2$ 个整数 $n,m$，表示位置的数量和道路的数量

之后 $m$ 行：每行 $2$ 个正整数 $u,v$，表示站点 $u$ 向 $v$ 有一条单向道路

输出数据

输出一个整数，表示至多开设的公交线路数量。

3 3
1 2
2 3
3 2

7

所有可行线路：$\{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 2), (3, 3)\}$

数据范围

• 对于 $12.5\%$ 的数据，$2\le N\le 10,0\le M \le10$
• 对于 $100\%$ 的数据，$2\le N\le 2000,0\le M \le min(2000,N(N-1))$
• $1\le u_i,v_i \le N,u_i \ne v_i$