4993.造花(困难版)

时间限制:4s 内存限制:256MB

给定一张无重边无自环的无向图,对于图中的每个点,如果将这个点和所有连向它的边删去后,整个图的所有极大连通子图都是菊花图,则称其为“混沌点”。请求出这张图的所有混沌点。

一个 $n$ 个点的连通图是菊花图,当且仅当它是一棵树,且至少有一个点与其它 $n−1$ 个点之间都有边直接相连。特别地,一个点的树也是菊花图。

输入格式(从终端/标准输入读取)

第一行一个整数 $T(1≤T≤10^5)$ 表示测试数据组数。

对于每组数据,第一行两个整数 $n$ 和 $m(2≤n≤10^4, 0≤m≤10^5)$,表示点数和边数。

接下来有 $m$ 行,每行两个整数 $u$ 和 $v($1≤u,v≤n)$,表示 $u$ 和 $v$ 之间有边连接。

数据保证所有图都没有重边且没有自环,但不保证连通。另外还保证 $∑n≤2×10^6, ∑m≤2×10^6$ 。

输出格式(输出至终端/标准输出)

对于每组测试数据,输出一行,如果这张图有混沌点,请将所有混沌点按序号从小到大的顺序输出,如果没有混沌点,请输出 $−1$。

输入样例

复制
3
3 3
1 2
2 3
1 3
2 0
4 6
1 2
1 3
1 4
2 3
2 4
3 4
 \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n

输出样例

复制
1 2 3
1 2
-1
 · · \n
 · \n
  \n

说明

由于本题读入量较大,推荐使用 $fread$ 函数进行数据读入。

来源: 2024“钉耙编程”中国大学生算法设计超级联赛(6)

提交题解

Please login first.

© 2025 FAQs