Championships

Time limit1.5sMemory limit256 MB

Summary

Find the largest set S of vertices such that the induced subgraph on S is connected and every vertex in S has degree at least d within S.

Level: Hard8 of 10
Topics: Graph, Greedy, BFS, Implementation
Solved: No attempts yet

Problem

The Computer Sports World Championships are 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 King Byteasar, faces a difficult task: it has to decide in which Byteotian cities the competitions will take place. Byteotia has $n$ cities (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. Naturally, 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 championship events is well connected.

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

From every city of the set $S$ there are at least $d$ direct connections to other cities of $S$ .
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 as large as possible.

Input

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 number of cities, the number of roads in Byteotia and the parameter $d$ , respectively. The 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.

Output

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.

Examples2

Example 1
Input
```
4 4 2
1 2
2 3
3 4
4 2
```
Expected output
```
3
2 3 4
```
Example 2
Input
```
3 2 2
1 2
2 3
```
Expected output
```
NIE
```