#P4296. [PA2015]Mistrzostwa

    ID: 3516 传统题 1000ms 256MiB 尝试: 276 已通过: 104 难度: 4 上传者: 标签>难度分类普及+/提高-数据结构队列模拟与实现技巧增量维护枚举与搜索广度优先搜索图论无向连通分量时间戳避免清空数组k-core 剥离CF1600ByClaris

[PA2015]Mistrzostwa

[PA2015] Mistrzostwa

题目描述

Bajtocia 将举办电子竞技锦标赛。为了方便观众在各个比赛城市之间往返,组委会要从 nn 座城市中选出一个非空集合 SS,并使它满足以下条件。

  • SS 中的每座城市都至少与 SS 中另外 dd 座城市有道路直接相连。
  • SS 中任意两座城市之间都有一条只经过 SS 中城市的路线。

求一个城市数最多的可行集合 SS。

输入格式

第一行三个整数 n,m,dn,m,d,表示城市数、双向道路数和最低邻居数。

接下来 mm 行,每行两个整数 ai,bia_i,b_i,表示两座城市之间有一条双向道路。任意两座城市之间至多有一条直接道路。

输出格式

无解时输出一行 NIE。

有解时,第一行输出 k=∣S∣k=|S|,第二行按编号递增的顺序输出所选的 kk 座城市。若有多个最大的集合,按原赛规则可以输出任意一个。

样例 #1

样例输入 #1

4 4 2
1 2
2 3
3 4
4 2

样例输出 #1

3
2 3 4

样例 #2

样例输入 #2

3 2 2
1 2
2 3

样例输出 #2

NIE

数据规模与约定

2≤n≤2000002\le n\le200000,1≤m≤2000001\le m\le200000,1≤d<n1\le d<n,1≤ai,bi≤n1\le a_i,b_i\le n,ai≠bia_i\ne b_i。

原赛题面