선수권 대회

전산 스포츠 세계 선수권 대회는 모든 전자 오락 팬들의 달력에서 가장 중요한 행사이다. 올해는 선수권 대회의 개최가 바이토치아 왕국의 몫으로 돌아갔다. 왕 바이타자르가 임명한 조직 위원회는 어려운 과제에 직면해 있다. 바이토치아의 어느 도시에서 경기를 개최할지 결정해야 한다. 바이토치아에는 n개의 도시(1부터 n까지 번호가 매겨짐)가 있고 m개의 양방향 도로로 연결되어 있다.

위원회는 전 세계에서 수많은 팬들이 선수권 대회에 올 것으로 예상한다. 팬들은 여러 종목의 경기를 관람하기 위해 개최 도시들 사이를 자주 이동할 것이다. 따라서 경기가 열리는 도시 집합이 잘 연결되어 있어야 한다는 것이 최우선이다.

도시 집합 S를 잘 연결되어 있다고 부르는 조건은 다음과 같다.

1. 집합 S의 모든 도시에서 집합 S의 다른 도시로 가는 직접 도로가 최소 d개 나온다.
2. 집합 S의 임의의 두 도시 사이에 집합 S의 도시들만 지나는 경로가 존재한다.

또한 도시당 평균 방문객 수를 최소화하기 위해 위원회는 선택한 집합이 가능한 한 크기를 원한다.

첫 번째 줄에는 세 개의 정수 n, m, d가 주어진다(2 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000, 1 ≤ d < n). 각각 바이토치아의 도시 수와 도로 수, 그리고 매개변수 d를 나타낸다. 다음 m개의 줄에는 바이토치아의 도로에 대한 설명이 주어진다. i번째 줄에는 두 개의 정수 ai와 bi가 주어진다(1 ≤ ai, bi ≤ n, ai ≠ bi). i번째 도로가 번호 ai와 bi인 도시를 연결한다는 뜻이다. 두 도시 사이에는 직접 도로가 최대 하나만 존재한다.

바이토치아에서 잘 연결된 도시 집합을 선택할 수 없다면, 출력에 NIE라는 단어를 출력해야 한다.

그렇지 않다면, 가장 큰 잘 연결된 도시 집합을 다음 형식으로 출력해야 한다. 첫 번째 줄에는 찾은 집합의 크기 k가 있어야 한다. 두 번째 줄에는 집합에 속하는 도시의 번호 k개를 오름차순으로 출력해야 한다.

여러 해가 존재한다면, 프로그램은 그중 어느 것이든 출력할 수 있다.