Canadian Computing Olympiad: 2016 Day 1, Problem 1

As a special treat for your kindergarten class, you're taking them on a field trip to a magical place of wonder.

Your class has ~N~ students, numbered from ~1~ to ~N~ for convenience. There are ~M~ direct, two-way friendships that exist between the students. Each student is friends with at most two other students.

Aside from the ~M~ direct friendships, students may also be acquainted with one another. Two students ~i~ and ~j~ are acquaintances if they're friends, or if there exists a third student ~k~ who is an acquaintance of both students ~i~ and ~j~. For example, if ~(1, 2)~, ~(2, 3)~, ~(3, 4)~ and ~(4, 5)~ are pairs of students with a direct friendship, then person ~1~ and person ~5~ are acquaintances.

You're getting ready to order buses for the trip, but there are two issues. Firstly, the transportation company insists that every bus you order must be filled exactly to its capacity of ~K~ students. They won't allow you to order a bus if you intend to put fewer than ~K~ students on it! Secondly, the students are picky about their travelling conditions. Each student ~i~ will refuse to get on a bus unless both of the following conditions are met:

• All of the other students getting on that bus are acquaintances of student ~i~;
• All of student ~i~'s acquaintances are getting on that bus.

Unfortunately, it looks like you might not be able to bring your whole class on this trip after all. However, you'll do whatever it takes to get as many students as possible on buses. As it turns out, "whatever it takes" may involve putting an end to a friendship or two, for the greater good. You may choose to sever ~0~ or more of the ~M~ friendships amongst the students, which will of course also have an effect on which students are acquainted with one another.

Determine the maximum number of students which can be brought on the trip, such that they're loaded onto buses with exactly ~K~ students each, and every student is satisfied with their bus allocation. Furthermore, since you're feeling generous, determine the minimum number of friendships which you can sever in order to be able to bring that many students along.

Input Specification

The first line contains three space-separated integers ~N~, ~M~ and ~K~ ~(1 \le N \le 10^6~; ~0 \le M \le 10^6~; ~1 \le K \le N)~.

The next ~M~ lines contain information about the friendships. That is, each of these ~M~ lines contain two space-separated integers ~A_i~ and ~B_i~ ~(1 \le i \le M)~ describing that students ~A_i~ and ~B_i~ are friends ~(1 \le A_i, B_i \le N, A_i \neq B_i)~. Note that no friendship is specified twice (that is, no two unordered friendship pairs are equal to one another).

For ~3~ of the ~25~ marks available, ~N \le 1000~.

Output Specification

The output consists of two space-separated integers printed on one line. The first integer is the maximum number of students which can be brought on the trip. The second integer is the minimum number of friendships which must be severed in order to bring that many students.

Sample Input

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

Sample Output

6 2

Explanation

If the friendships between student pairs ~(8,2)~ and ~(4,5)~ are severed, then ~3~ buses can be filled as follows:

• Bus ~1~: Students ~1~ and ~4~
• Bus ~2~: Students ~2~ and ~6~
• Bus ~3~: Students ~3~ and ~5~