题目描述

作为给幼儿园小朋友的特别福利，你带他们去一个神奇的奇妙之地郊游。

你班上有 $N$ 名学生，为了方便起见，学生编号从 $1$ 到 $N$。学生之间有 $M$ 条直接的双向友谊。每个学生最多有两个朋友。

除了这 $M$ 条直接友谊外，学生之间还可能是“熟人”。如果两个学生 $i$ 和 $j$ 是朋友，或者存在第三个学生 $k$ 同时是 $i$ 和 $j$ 的熟人，那么这两个学生也是熟人。举个例子，如果 $(1, 2)$、$(2, 3)$、$(3, 4)$ 和 $(4, 5)$ 是直接朋友，那么学生 $1$ 和学生 $5$ 就是熟人。

你正准备订购校车，但遇到两个难题。首先，运输公司规定每辆校车必须恰好坐满 $K$ 名学生，不能少于 $K$ 人；其次，学生们对乘车条件很挑剔。每个学生 $i$ 只有满足以下两条，才愿意上车：

1. 同车的其他学生都必须是该学生的熟人；
2. 该学生的所有熟人都必须坐在同一辆车上。

看起来你可能没法带全班同学去郊游了。不过你会尽力让尽可能多的学生上车。为此，“尽力”可能意味着要断掉一两段友谊，牺牲小部分感情换取大局。你可以选择断开 $0$ 条或更多的 $M$ 条友谊，这也会影响学生间的熟人关系。

请你计算，最多能带多少学生去郊游，且他们能被分配到恰好坐满 $K$ 人的校车上，同时每个学生都满意自己的座位安排。另外，既然你心地善良，还要算出为了带这么多学生，最少需要断开多少条友谊。

输入格式

第一行包含三个用空格分隔的整数 $N$、$M$ 和 $K$（$1 \le N \le 10^6,0 \le M \le 10^6,1 \le K \le N$）。

接下来 $M$ 行，每行包含两个用空格分隔的整数 $A_i$ 和 $B_i\ (1 \le i \le M)$，表示学生 $A_i$ 和 $B_i$ 是朋友（$1 \le A_i, B_i \le N, A_i \neq B_i$）。注意没有重复的友谊对。

对于 $25$ 分中的 $3$ 分，$N \le 1000$。

输出格式

输出一行，包含两个用空格分隔的整数。第一个是最多能带去郊游的学生人数，第二个是为此最少需要断开的友谊数。

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$

翻译来源：GPT 4.1 mini。