F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 4155. -- [Ipsc2015]Humble Captains

4155: [Ipsc2015]Humble Captains

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 350  Solved: 145
[Submit][Status][Discuss]

Description

每天下午放学时都有n个zky冲出教室去搞基。搞基的zky们分成两队,编号为1的zky是1号队的首领,编号为2的zky是2号队的首领。其他的zky可以自由选择是去1队还是2队。
zky们当中有几对zky是好基友(同一个zky可能在多对“好基友”关系中),如果一对好基友在同一个队,那么这个队的战斗力就+1。
现在你要解决两个问题:1.两队战斗力之和最大是多少?2.两队战斗力之差的绝对值最小是多少?
注意:这两个问题是不相关的。也就是说,问1和问2的方案可以是不一样的。

Input

第一行t表示数据组数
每一组测试数据的第一行包含两个整数n,m,zky们编号从1到n,共有m对好基友关系。
接下来m行每行两个整数u和v,表示u和v之间存在好基友关系。保证每一对好基友关系只会被描述一次。

Output

对每一组,输出一行两个数,第一个是最大战斗力之和,第二个是最小战斗力之差。

Sample Input

2
3 3
1 2
2 3
1 3

3 1
1 3

Sample Output

1 1
1 0

HINT

n <= 200, t <= 250


Source

[Submit][Status][Discuss]

HOME Back