该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目限制
1000 ms 256 M
题目描述
自从有了立体交通,道路不再受平面的限制,可以不用有十字路口,就让两条道路互相穿越。
已知城市中共有 n 个站点(编号 1∼n ),其中共有 m 条单向道路。现在公交公司计划开设一些单行线的公交线路,需要保证起始站 s 向终点站 t 有通路连接,并且同一组 (s,t) 仅开设一条线路。
现在请问至多能够开设多少条线路?
注意:允许存在环线,即 s=t 。且由于是单行线, (s,t) 与 (t,s) 视为不同线路。
输入格式
第一行: 2 个整数 n,m ,表示位置的数量和道路的数量。( 2≤N≤2000 , 0≤M≤min(2000,N(N−1)) )
之后 m 行:每行 2 个正整数 u,v ,表示站点 u 向 v 有一条单向道路,保证不存在自环。
输出格式
输出一个数表示至多开设的公交线路数量。
数据范围
对于 12.5% 的数据, 2≤N≤10,0≤M≤10 ;
对于 100% 的数据, 2≤N≤2000,0≤M≤min(2000,N(N−1)),1≤ai,bi≤N,ai=bi 。
输入样例 1
3 3
1 2
2 3
3 2
输出样例 1
7