F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

造花(困难版)

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 363    Accepted Submission(s): 120


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

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

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

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

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

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

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

Sample Input
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
 

Sample Output
1 2 3 1 2 -1
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-09-20 05:54:51, Gzip enabled