#P18676. Classical Graph Theory Problem

    ID: 18012 传统题 4000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-一般图匹配不变量分析对称性分析增量维护

Classical Graph Theory Problem

Classical Graph Theory Problem

给定一个连通的无向图 G=(V,E)G=(V,E)。

如果每个顶点 v∈Vv\in V 要么属于集合 SS,要么至少有一个邻居属于 SS,则称 SS 为图的一个支配集。

一个顶点恰好有一个邻居时,称它为叶子。图满足:每个顶点的邻居中,至多有两个叶子。

请找出一个顶点集合 S⊂VS\subset V,同时满足:

  1. SS 是图 GG 的支配集;
  2. V∖SV\setminus S 也是图 GG 的支配集;
  3. ∣S∣=⌊∣V∣/2⌋|S|=\lfloor |V|/2\rfloor。

保证满足要求的集合一定存在。

输入格式

每份输入包含多组测试。第一行是测试组数 tt(1≤t≤1041\le t\le 10^4)。随后依次给出各组。

每组第一行是两个整数 n,mn,m,分别表示顶点数和边数(2≤n≤2⋅1052\le n\le 2\cdot10^5,1≤m≤5⋅1051\le m\le5\cdot10^5)。

接下来的 mm 行,每行有两个整数 xi,yix_i,y_i,表示第 ii 条边的两个端点(1≤xi,yi≤n1\le x_i,y_i\le n,xi≠yix_i\ne y_i)。图连通,没有自环或重边,每个顶点至多有两个叶子邻居。

保证所有测试组的 nn 之和不超过 2⋅1052\cdot10^5,mm 之和不超过 5⋅1055\cdot10^5。

输出格式

对每组测试,输出 ⌊n/2⌋\lfloor n/2\rfloor 个互不相同的整数 s1,s2,…,s⌊n/2⌋s_1,s_2,\ldots,s_{\lfloor n/2\rfloor},表示集合 SS 的顶点,顺序任意,编号均在 11 到 nn 之间。

有多个合法答案时,输出其中任意一个。不需要输出集合大小。

样例输入 1

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

样例输出 1

2 3 6
2