19488번 - Championships 스페셜 저지다국어

문제

The Computer Sports World Championships is the most important event in the calendar of every electronic entertainment fan. This year, the championships will be held in the kingdom of Byteotia. The organizing committee, appointed by the king Byteasar, is facing a difficult task -- it has to decide in which Byteotian cities competitions will take place. There are $n$ cities in Byteotia (numbered 1ドル$ through $n$) connected by $m$ two-way roads.

The committee hopes that the championship will attract crowds of fans from all over the world. Obviously, the fans will travel frequently between the cities to watch the competitions of various e-sport types. The priority is therefore that the set of cities, hosting the championships events, is well connected.

We call a set of cities $S$ well connected, if:

1. From every city of the set $S$ there are at least $d$ direct connections to other cities of $S$.
2. Between any two cities of $S$ there exists a route running only through the cities belonging to the set $S$.

Additionally, to minimize the average number of visitors in each city, the committee would prefer the chosen set to be possibly large.

입력

The first line of the input contains three integers $n,ドル $m$ and $d$ (2ドル\leq n\leq 200,000円,ドル 1ドル\leq m\leq 200,000円,ドル 1ドル\leq d < n$) denoting the the number of cities, the number of roads in Byteotia and the parameter $d,ドル respectively. Next $m$ lines describe the Byteotian roads. The $i$-th of these lines contains two integers $a_i$ and $b_i$ (1ドル\leq a_i,b_i\leq n,ドル $a_i\neq b_i$) indicating that the $i$-th road connects the cities numbered $a_i$ and $b_i$. Each pair of cities is connected by at most one direct road.

출력

If it is not possible to choose a set of cities of Byteotia that is well connected, the only line of the output should contain the word "NIE" (Polish for no).

Otherwise, the output should contain the most numerous set of cities that is well connected, in the following format. The first line should contain the number $k$ denoting the size of the found set. The second line should contain $k$ numbers representing the cities belonging to the set, in ascending order.

In case there are multiple solutions, your program can output any of them.

제한

힌트