#P18614. Group Guests

Group Guests

Group Guests

一次聚会上有 nn 位客人。每位客人恰好有两种不同的爱好,任意两位客人的爱好集合都不相同。

主持人想把一些客人分成若干个组,每组有两人或三人,组内任意两人都至少有一种共同爱好。每组恰好属于下列类型之一:

  • A 型:两人组成一组,两人有一种共同爱好。
  • B 型:三人组成一组,三人都有同一种爱好。
  • C 型:三人组成一组,任意两人都有一种共同爱好,但不属于 B 型。

每位客人至多进入一个组,也可以不进入任何组。

首先,要让没有分到任何组的客人数 α\alpha 尽可能少。在 α\alpha 已经最小的前提下,再让使用的 B 型组数 β\beta 尽可能少。

请输出最优的 α\alpha 和 β\beta,无需输出具体分组。

图15:第三个样例的两种分组

图 15 给出第三个样例的两种分组。左右两种方案都让所有客人进入某个组,但右边不使用 B 型组,因此更优。

输入格式

输入只有一组数据。

第一行两个整数 n,hn,h,分别表示客人数和爱好编号的上界。

接下来 nn 行,每行两个整数 x,yx,y,表示该客人的两种爱好,满足 1≤x,y≤h1\le x,y\le h、x≠yx\ne y。保证任意两行代表的无序对不相同。

不要求每个爱好编号都出现。

输出格式

输出两个整数 α,β\alpha,\beta,分别为最少的未分组客人数,以及在此基础上最少的 B 型组数。

数据范围

  • 2≤n≤1062\le n\le10^6。
  • 3≤h≤2n3\le h\le2n。

样例输入 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