통신 파트너

국제 통신 회사가, 고객 기업이 지정한 특정 전화번호로 거는 통화에 대해 할인을 제공하려고 한다. 지난 한 해 동안의 통화 기록으로부터, 두 회사 중 한쪽이 다른 쪽에게 통화를 걸거나 받은 적이 있으면 그 두 회사를 비즈니스 파트너라고 부른다.

회사들 사이의 파트너 관계와 정수 $K$가 주어질 때, 다음 두 조건을 모두 만족하는 회사 집합 $S$ 중 가장 큰 것의 크기(회사 수)를 구하라.

• $S$에 속한 모든 회사는 $S$ 안에 있는 비즈니스 파트너를 적어도 $K$개 가진다. ($S$ 밖에 있는 파트너는 있어도 되고 없어도 된다.)
• $S$는 연결되어 있다. 즉, $S$ 안의 임의의 회사에서 $S$ 안의 다른 임의의 회사로, $S$에 속한 회사들 사이의 파트너 관계만 따라가서 도달할 수 있다.

이러한 집합이 존재하지 않으면 답은 $0$이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 세 정수 $N$, $P$, $K$가 주어진다. $N$은 통신사에 가입한 전체 회사 수이며 ($1 \le N \le 1000$), 회사는 $1$부터 $N$까지의 번호로 식별된다. $P$는 비즈니스 파트너 쌍의 개수이고, $K$는 최종 집합에서 각 회사가 가져야 하는 최소 파트너 수이다 ($1 \le K \le N-1$).

이어지는 $P$개의 줄에는 각각 두 정수 $X$와 $Y$가 주어지며 ($1 \le X \le N$, $1 \le Y \le N$, $X \ne Y$), 회사 $X$와 $Y$가 비즈니스 파트너임을 뜻한다. 같은 쌍이 여러 줄에 나올 수 있으나, 이는 하나의 파트너 관계로만 센다.

첫 정수 $N$이 $0$인 줄은 입력의 끝을 나타낸다.

각 테스트 케이스마다, 위 조건을 만족하는 가장 큰 집합 $S$의 크기를 한 줄에 출력한다.