#P18614. Group Guests
Group Guests
Group Guests
一次聚会上有 位客人。每位客人恰好有两种不同的爱好,任意两位客人的爱好集合都不相同。
主持人想把一些客人分成若干个组,每组有两人或三人,组内任意两人都至少有一种共同爱好。每组恰好属于下列类型之一:
- A 型:两人组成一组,两人有一种共同爱好。
- B 型:三人组成一组,三人都有同一种爱好。
- C 型:三人组成一组,任意两人都有一种共同爱好,但不属于 B 型。
每位客人至多进入一个组,也可以不进入任何组。
首先,要让没有分到任何组的客人数 尽可能少。在 已经最小的前提下,再让使用的 B 型组数 尽可能少。
请输出最优的 和 ,无需输出具体分组。

图 15 给出第三个样例的两种分组。左右两种方案都让所有客人进入某个组,但右边不使用 B 型组,因此更优。
输入格式
输入只有一组数据。
第一行两个整数 ,分别表示客人数和爱好编号的上界。
接下来 行,每行两个整数 ,表示该客人的两种爱好,满足 、。保证任意两行代表的无序对不相同。
不要求每个爱好编号都出现。
输出格式
输出两个整数 ,分别为最少的未分组客人数,以及在此基础上最少的 B 型组数。
数据范围
- 。
- 。
样例输入 1
2 4
1 2
3 4
样例输出 1
2 0
样例输入 2
2 3
1 2
3 1
样例输出 2
0 0
样例输入 3
5 5
1 2
2 3
2 4
5 2
5 4
样例输出 3
0 0