현장 학습

유치원 반 아이들에게 주는 특별한 선물로, 신기한 구경거리가 있는 곳에 현장 학습을 간다.

반에는 학생이 $N$명 있고, 편의상 $1$번부터 $N$번까지 번호를 붙인다. 학생 사이에는 양방향 친구 관계가 $M$개 있다. 한 학생은 많아도 두 명과 친구다.

$M$개의 직접적인 친구 관계 말고도 학생끼리 서로 아는 사이일 수 있다. 학생 $i$와 학생 $j$는 둘이 친구이거나, 학생 $i$와도 아는 사이이고 학생 $j$와도 아는 사이인 다른 학생 $k$가 있으면 아는 사이다. 예를 들어 $(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$개 줄에는 친구 관계가 주어진다. 각 줄에는 정수 $A_i$와 $B_i$가 공백으로 구분되어 주어지고 ($1 \le i \le M$), 학생 $A_i$와 학생 $B_i$가 친구라는 뜻이다 ($1 \le A_i, B_i \le N$, $A_i \ne B_i$). 같은 친구 관계가 두 번 주어지는 일은 없다. 즉 순서를 무시한 친구 쌍 두 개가 서로 같은 경우는 없다.

한 줄에 정수 두 개를 공백으로 구분해 출력한다. 첫 번째 정수는 현장 학습에 데려갈 학생 수의 최댓값이고, 두 번째 정수는 그만큼 데려가려고 끊어야 하는 친구 관계 수의 최솟값이다.