题目描述

译自 CCO 2016 Day1 T1「Field Trip」。

为了奖励可爱的小朋友们，你决定带你的幼儿园班级去一个充满神奇和惊喜的地方进行一次户外教学。

你的班级一共有 $N$ 个小朋友，为了方便起见，我们给他们编号从 $1$ 到 $N$。其中有 $M$ 对小朋友是好朋友，每个小朋友最多有两个好朋友。

除了直接的好朋友关系外，小朋友们还可能有认识的关系。如果两个小朋友是好朋友，或者他们都有一个共同的认识的人，那么他们就被认为是认识的。比如说，如果 $1$ 和 $2$、$2$ 和 $3$、$3$ 和 $4$、$4$ 和 $5$ 是好朋友，那么 $1$ 和 $5$ 就是认识的。

现在你要为这次户外教学安排巴士，但是有两个问题：

1. 巴士公司要求每辆巴士必须坐满 $K$ 个小朋友，不能少于 $K$ 个。
2. 小朋友们对同行的伙伴很挑剔。每个小朋友只有在满足以下两个条件时才会上车：
   • 巴士上所有其他小朋友都和他是认识的。
   • 他所有的认识的人都在这辆巴士上。

不幸的是，看起来你可能无法带全班小朋友去旅行了。但是，你会尽一切努力让尽可能多的孩子上车。为了达到这个目的，你可能需要做出一些艰难的决定，比如拆散一些小朋友之间的友谊。你可以选择切断 $0$ 个或多个小朋友之间的友谊，这也会影响到小朋友之间的认识关系。

你需要计算出在保证每辆巴士正好坐满 $K$ 个小朋友，且所有小朋友都对自己的巴士安排满意的情况下，最多能有多少个小朋友能参加这次旅行，和为了达到这个目标，最少需要切断多少对小朋友之间的友谊。

输入格式

第一行包含三个用空格分隔的整数 $N, M, K$。接下来的 $M$ 行包含关于友谊的信息。每一行包含两个用空格分隔的整数 $A_i,B_i$，表示学生 $A_i$ 和 $B_i$ 是朋友。没有两个无序的朋友对是相同的。

输出格式

输出一行包含两个用空格分隔的整数。第一个整数是最多能参加旅行的小朋友数量，第二个整数是达到这个目标最少需要切断的友谊数量。

8 5 2
1 4
8 2
4 5
6 2
3 5

6 2

如果切断学生 $8$ 和 $2$、$4$ 和 $5$ 之间的友谊，那么可以安排 $3$ 辆巴士如下：

• 巴士 $1$：学生 $1$ 和 $4$
• 巴士 $2$：学生 $2$ 和 $6$
• 巴士 $3$：学生 $3$ 和 $5$

数据范围与提示

对于 $12\%$ 的数据，$N \leq 1000$；
对于 $100\%$ 的数据，$1 \leq N \leq 10^6, 0 \leq M \leq 10^6, 1 \leq K \leq N$；$1 \leq A_i, B_i \leq N, A_i \neq B_i\ (1\leq i\leq M)$。