The World Computer Sports Championships are the most important event in the calendar of every fan of electronic entertainment. This year, the organization of the championships has fallen to the kingdom of Byteotia. The organizing committee appointed by King Bajtazar faces a difficult task – it must decide in which cities of Byteotia the competitions will be held. There are $n$ cities in Byteotia (numbered from $1$ to $n$) connected by $m$ bidirectional roads.

The committee expects crowds of fans from all over the world to arrive for the championships. It is known that fans will frequently travel between the host cities to watch competitions in various disciplines. Therefore, the priority is for the set of cities where the competitions will be held to be well-connected.

A set of cities $S$ is called well-connected if: (1) From every city in the set $S$, there are at least $d$ direct roads to other cities in the set $S$. (2) Between any two cities in the set $S$, there exists a route passing only through cities in the set $S$.

Additionally, to minimize the average number of guests per city, the committee would like the chosen set to be as large as possible.

Input

The first line of input contains three integers $n$, $m$, and $d$ ($2 \le n \le 200\,000$, $1 \le m \le 200\,000$, $1 \le d < n$), representing the number of cities, the number of roads in Byteotia, and the parameter $d$, respectively. The next $m$ lines contain the description of the Byteotian roads: the $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$), meaning that the $i$-th road connects cities numbered $a_i$ and $b_i$. There is at most one direct road between any pair of cities.

Output

If it is not possible to choose a well-connected set of cities in Byteotia, output the word NIE. Otherwise, output the largest well-connected set of cities in the following format. The first line should contain the number $k$ representing the size of the found set. The second line should contain $k$ numbers representing the city numbers belonging to the set, in increasing order.

If there are multiple solutions, your program may output any one of them.

Examples

Input 1

4 4 2
1 2
2 3
3 4
4 2

Output 1

3
2 3 4

Input 2

3 2 2
1 2
2 3

Output 2

NIE