题目限制

1000 ms 256 M

题目描述

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

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

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

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

输入格式

第一行： $2$ 个整数 $n,m$ ，表示位置的数量和道路的数量。（ $2\le N\le 2000$ ， $0\le M\le min(2000,N(N-1))$ ） 之后 $m$ 行：每行 $2$ 个正整数 $u,v$ ，表示站点 $u$ 向 $v$ 有一条单向道路，保证不存在自环。

输出格式

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

数据范围

对于 $12.5\%$ 的数据， $2 \le N \le 10, 0 \le M \le 10$ ；

对于 $100\%$ 的数据， $2 \le N \le 2000, 0 \le M \le \min(2000,N(N-1)), 1 \le a_i,b_i \le N, a_i \ne b_i$ 。

输入样例 1

3 3
1 2
2 3
3 2

输出样例 1

7