챔피언십

컴퓨터 스포츠 세계 선수권은 모든 전자 오락 팬들의 달력에서 가장 중요한 행사이다. 올해 선수권은 바이트오티아 왕국에서 열린다. 국왕 바이테아사르가 임명한 조직위원회는 어려운 과제에 직면해 있다. 바이트오티아의 어느 도시에서 경기가 열릴지 결정해야 하는 것이다. 바이트오티아에는 $n$개의 도시(번호 $1$부터 $n$)가 있고 $m$개의 양방향 도로로 연결되어 있다.

조직위원회는 선수권이 전 세계에서 팬들을 끌어모을 것으로 기대한다. 팬들은 다양한 종목의 경기를 보기 위해 도시 사이를 자주 이동할 것이다. 따라서 우선순위는 선수권 경기를 개최하는 도시 집합이 잘 연결되어 있는 것이다.

도시 집합 $S$가 잘 연결되어 있다는 것은 다음을 만족한다는 뜻이다.

1. 집합 $S$의 모든 도시에서 $S$의 다른 도시로 가는 직접 연결이 적어도 $d$개 있다.
2. $S$의 임의의 두 도시 사이에 $S$에 속한 도시만을 지나는 경로가 존재한다.

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

입력의 첫 줄에는 세 정수 $n$, $m$, $d$가 주어진다($2\leq n\leq 200\,000$, $1\leq m\leq 200\,000$, $1\leq d < n$). 이는 각각 도시의 수, 바이트오티아의 도로 수, 매개변수 $d$를 나타낸다. 다음 $m$개의 줄은 바이트오티아의 도로를 설명한다. 이 중 $i$번째 줄에는 두 정수 $a_i$와 $b_i$($1\leq a_i,b_i\leq n$, $a_i\neq b_i$)가 주어지며, $i$번째 도로가 번호 $a_i$와 $b_i$인 도시를 연결한다는 뜻이다. 각 도시 쌍은 최대 하나의 직접 도로로 연결된다.

바이트오티아에서 잘 연결된 도시 집합을 선택할 수 없다면, 출력의 유일한 줄에 "NIE"(폴란드어로 아니오)를 출력한다.

그렇지 않다면, 가장 큰 잘 연결된 도시 집합을 다음 형식으로 출력한다. 첫 줄에는 찾은 집합의 크기 $k$를 출력한다. 둘째 줄에는 집합에 속한 도시를 나타내는 $k$개의 수를 오름차순으로 출력한다.

여러 해가 존재하는 경우, 프로그램은 그중 아무거나 출력해도 된다.