4296 - [PA2015]Mistrzostwa

给定一张n个点m条边的无向图，请找到一个点数最多的点集S，满足： 1.对于点集中任何一个点，它至少与d个点集中的点相邻。 2.仅保留点集中的点后，剩下的图连通。

Input

第一行包含三个正整数n,m,d(2<=n<=200000，1<=m<=200000，1<=d<n)，分别表示点数，边数以及度数限制。 接下来m行，每行包含两个正整数a,b(1<=a,b<=n，a不等于b)，表示a点和b点之间有一条边。

Output

若无解，输出NIE。 否则第一行输出一个正整数k，表示你找到的点数最多的点集S的点数。 第二行输出k个正整数，按升序依次输出点集中的点的编号，若有多组解，输出任意一组。

Examples

Input

4 4 2
1 2
2 3
3 4
4 2

Output

3
2 3 4

Hint

请不要提交，尚无SPJ

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题