最多边数
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
一张有向图含有 个点, 条边。点的编号为 ~ 。没有重边,也没有自环。
现在你希望再添加一些边。添加边的规则是:
若图中存在有向边 <a,b> 和 <a,c>,则你可以添加边 <b,c> 和 <c,b>。如果要添加的边已经存在,则无需添加。
你可以不断在新图中按以上规则进行加边。
问:最终图中最多包含多少条边?
输入格式
第一行:两个整数 和
接下来 行,每行两个整数 ,表示从点 向点 有一条有向边。
输出格式
一个整数,表示最终图中包含的最多边数。
样例输入
5 4
1 2
1 3
4 3
4 5
样例输出
10
数据范围
100% 的数据满足:
- ()
- ()
- ()
子任务
子任务 1 [5 分]
- 满足 。
子任务 2 [30 分]
- 满足 。
子任务 3 [65 分]
- 满足