#P1168. 关键枢纽

    ID: 180 传统题 1000ms 128MiB 尝试: 0 已通过: 0难度: 提高 ← 上一题 下一题 → 随机一题 上传者: 标签 图论 Tarjan 割点 DFS
显示设置

关键枢纽

题目描述

一张交通网里有 nn 座城市,编号 1∼n1\sim n,城市之间由 mm 条双向公路连接。

如果炸毁某座城市(连同与它相连的全部公路)之后,剩下的城市之间的连通块数量比原来更多,就称这座城市为「关键枢纽」。

请你找出全部关键枢纽。

输入格式

第一行两个整数 n,mn,m。

接下来 mm 行,每行两个整数 u,vu,v,表示一条连接 uu 与 vv 的公路。保证 1≤u<v≤n1\le u<v\le n,不存在重复的公路。

输出格式

第一行一个整数 kk,表示关键枢纽的数量。

第二行 kk 个整数,按编号从小到大输出这些城市;若 k=0k=0,第二行输出 −1-1。

输入输出样例 #1

输入 #1

6 5
1 2
2 3
3 1
3 4
4 5

输出 #1

2
3 4

说明

样例中炸毁 33 号城市后 {1,2}\{1,2\} 与 {4,5,6}\{4,5,6\} 分开,炸毁 44 号城市后 {5,6}\{5,6\} 与其余城市分开,因此二者都是关键枢纽。

数据范围

  • 对于 100%100\% 的数据,1≤n≤1051\le n\le 10^5,0≤m≤2×1050\le m\le 2\times 10^5。