Field Trip

As a special treat for your kindergarten class, you are 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 between the students. Each student is friends with at most two other students.

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

You are getting ready to order buses for the trip, but there are two problems. First, the transportation company insists that every bus you order is filled exactly to its capacity of $K$ students. They will not let you order a bus if you intend to put fewer than $K$ students on it. Second, the students are picky about their travelling conditions. Student $i$ refuses to get on a bus unless both of these conditions hold:

1. every other student getting on that bus is an acquaintance of student $i$;
2. every acquaintance of student $i$ is getting on that bus.

It looks like you cannot bring the whole class along after all. You will still do whatever it takes to get as many students as possible onto buses, and that includes ending a friendship or two for the greater good. You may sever $0$ or more of the $M$ friendships, which also changes who is acquainted with whom.

Determine the largest number of students you can bring on the trip, so that they are loaded onto buses holding exactly $K$ students each and every student is satisfied with the bus they are put on. Since you are feeling generous, also determine the smallest number of friendships you have to sever in order to bring that many students.

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$).

Each of the next $M$ lines describes one friendship. Line $i$ contains two space-separated integers $A_i$ and $B_i$ ($1 \le i \le M$), meaning that student $A_i$ and student $B_i$ are friends ($1 \le A_i, B_i \le N$, $A_i \ne B_i$). No friendship is given twice, so no two unordered friendship pairs are equal to each other.

Print two space-separated integers on one line. The first integer is the largest number of students you can bring on the trip. The second integer is the smallest number of friendships you have to sever in order to bring that many students.