为了给你的幼儿园班级提供一次特别的款待，你正带着他们去一个神奇的地方进行实地考察。

你的班级共有 $N$ 名学生，为了方便起见，编号为 $1$ 到 $N$。学生之间存在 $M$ 对直接的双向友谊。每名学生最多与另外两名学生是朋友。

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

你正准备为这次旅行预订巴士，但有两个问题。首先，运输公司坚持要求你预订的每辆巴士必须恰好坐满 $K$ 名学生。如果你打算在巴士上安排少于 $K$ 名学生，他们不允许你预订该巴士！其次，学生们对旅行条件很挑剔。每名学生 $i$ 除非满足以下两个条件，否则拒绝上车：

1. 车上所有其他学生都是学生 $i$ 的熟人；
2. 学生 $i$ 的所有熟人都在车上。

不幸的是，看起来你可能无法带全班同学参加这次旅行。然而，你会不惜一切代价让尽可能多的学生坐上巴士。事实证明，“不惜一切代价”可能意味着为了大局而结束一两段友谊。你可以选择切断 $M$ 对友谊中的 $0$ 条或多条，这当然也会影响学生之间谁是熟人。

确定可以参加旅行的学生的最大数量，使得他们被装载到每辆恰好有 $K$ 名学生的巴士上，并且每名学生都对他们的巴士分配感到满意。此外，由于你很慷慨，请确定为了带上这么多学生，你必须切断的最少友谊数量。

输入格式

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

接下来的 $M$ 行包含有关友谊的信息。即，这 $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$。

输出格式

输出由一行中两个空格分隔的整数组成。第一个整数是可以带去旅行的学生的最大数量。第二个整数是为了带上这么多学生而必须切断的最少友谊数量。

样例

输入 1

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

输出 1

6 2

说明 1

如果切断学生对 $(8, 2)$ 和 $(4, 5)$ 之间的友谊，那么可以填满 $3$ 辆巴士，如下所示：

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