#2159. 【AROI Round 2】朋友

【AROI Round 2】朋友

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

题目描述

小明在初一(1)班,小刚在初一(2)班,两个班各有 nn 个人,编号为 1n1-n。这两个班之间非常和睦,任意两个人不是仇人,两个班之间有 mm 条好友关系。级长王老师想让 nn 对不同班的好友分别组成 nn 组。当然,王老师可能要让几对不同班的不认识的同学变为好友,每把 11 对不同班的不认识的同学变为好友需要 1010 分钟。她不想花太多的时间在这上,你能求出她需要的最小时间吗?

输入格式

第一行两个正整数 n,mn,m

接下来 mm 行,每行 22 个数 x,yx,y,表示一班的 xx 号同学和二班的 yy 号同学是好友。

输出格式

输出最小时间。

样例 #1

样例输入 #1

5 7
1 2
1 3
1 4
1 5
2 5
3 5
4 5

样例输出 #1

30

提示

王老师可以让一班的 22 号同学和二班的 11 号同学变为好友;再让一班的 33 号同学和二班的 33 号同学变为好友;最后让一班的 55 号同学和二班的 44 号同学变为好友。

这样一班的 11 号和二班的 22 号组队,一班的 22 号和二班的 11 号组队,一班的 33 号和二班的 33 号组队,一班的 44 号和二班的 55 号组队,一班的 55 号和二班的 44 号组队,总共要 33 次,需要 3030 分钟。

1n,m10001\le n,m\le1000

AROI Round 2&temege月赛3

未参加
状态
已结束
规则
IOI
题目
6
开始于
2022-7-8 18:30
结束于
2022-7-15 18:30
持续时间
168 小时
主持人
参赛人数
10