#P11811. [PA 2015] 人赢 / Mistrzostwa

    ID: 13065 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>图论2015并查集Special JudgePA(波兰)

[PA 2015] 人赢 / Mistrzostwa

题目背景

译自 PA 2015 R2.

题目描述

给定一张 nn 个点 mm 条边的简单(无重边自环的)无向图 G=(V,E)G=(V,E)。其中节点编号 1n1\sim n

给定正整数 dd。选出一个最大的点集 SVS\subseteq V,满足:

  • uS\forall u\in SvS[(u,v)E]d\displaystyle \sum_{v\in S} [(u,v)\in E]\ge d。换句话说,uuSS 内点至少连了 dd 条边。
  • SS 的导出子图(induced subgraph)是连通的。

你需要构造一个 SS 使得 S|S| 取到最大值,或者报告无解。

点集 VVV'\subseteq V 的导出子图定义为 G=(V,E)G'=(V',E'),其中 E={(u,v)E:uVvV}E'=\{(u,v)\in E: u\in V'\land v\in V'\}

输入格式

第一行,三个正整数 n,m,dn,m,d

接下来 mm 行,每行两个正整数 u,vu,v,表示 (u,v)E(u,v)\in E

输出格式

如果符合条件的 SS 不存在,输出一行一个 NIE\texttt{NIE}

否则,第一行输出 S|S|,第二行升序输出 SS 中节点的编号。

4 4 2
1 2
2 3
3 4
4 2
3
2 3 4
3 2 2
1 2
2 3
NIE

提示

  • 1d<n2×1051\le d\lt n\le 2\times 10^5
  • 1m2×1051\le m\le 2\times 10^5
  • 给定的图无重边自环。