[AdditionalFile5526.zip](file://AdditionalFile5526.zip?type=additional_file)

#5526. 「COI 2025」Lirili Larila

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 COI 2025 T4「Lirili Larila」

苏格拉底：柏拉图，关于这一点，你同意我的看法吗：最强的战士是那些会飞的，比如轰炸机·克罗克迪拉（Bombardira Crocodilla）或邦邦比尼·古西尼（Bombombinija Gusinija）。

柏拉图：此言差矣。陆地战士，比如呜呜·帕塔皮马（Brr Brr Patapima）或咚咚咚·萨胡拉（Tung Tung Tung Sahura），他们取得的成就是尽管没有飞行能力的情况下完成的。

苏格拉底：我认为，我们通往真理的唯一途径就是让战士们去战斗，并根据结果来判定胜负。

柏拉图：说得好，苏格拉底，我同意这样我们就能找到真理。

决战将在一个有 $N$ 个节点和 $M$ 条边的连通图上进行。莉莉莉·拉莉拉，半是大象半是仙人掌，是这个图的所有者，所以她将确保这会是她最喜欢的一种图：仙人掌图。为本题之目的，我们将仙人掌图定义为一个简单的连通图，其中每个节点最多属于一个环。

战斗按以下方式进行。开始时，所有飞行战士被放置在一个特定的起始节点，而所有陆地战士被放置在另一个起始节点。随着战斗的进行，战士们在图上扩大他们的影响力，并试图征服尽可能多的节点。最终，一个节点将被飞行战士或陆地战士征服，这取决于该节点与飞行战士的起始节点更近，还是与陆地战士的起始节点更近。与飞行和陆地战士起始节点距离相等的节点对双方来说都是一个巨大的挑战，因此它们将保持未被征服的状态。

莉莉莉·拉莉拉想要操纵战斗的结果。实际上，她已经预先确定了自然数 $A$ 和 $B$，分别代表飞行战士和陆地战士征服的节点数量。请帮助这位可爱的仙人掌-大象，为两种战士选择起始节点，以便在战斗结束时，被征服的节点数量恰好对应于数字 $A$ 和 $B$。

此外，你需要为 $T$ 种不同的情形做出这样的选择。

输入格式

第一行是一个自然数 $T$，代表不同情形的数量。

接下来的行依次是各种情形的描述。每个描述都按以下格式给出。

第一行是自然数 $N, M, A$ 和 $B$，分别代表给定仙人掌图中的节点数和边数，以及飞行战士和陆地战士要征服的节点数。

接下来的 $M$ 行是数对 $a$ 和 $b$ $(1 \leq a, b \leq N, a \neq b)$，代表图的边。

给定的图将是一个仙人掌图，即一个简单的连通图，其中每个节点最多属于一个环。

测试数据将保证总能找到满足题目条件的起始节点选择。

输出格式

输出 $T$ 行，每种情况一行。

在第 $i$ 行，输出两个用空格隔开的自然数，代表飞行战士和陆地战士的起始节点，即第 $i$ 种情况所期望的选择。如果存在多种解，输出任意一种即可。

样例 1

输入

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

输出

4 3

飞行战士征服了节点 $4, 5, 6$，而陆地战士征服了节点 $3$。节点 $1$ 和 $2$ 仍未被征服。

样例 2

输入

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

输出

1 6

飞行战士征服了节点 $1, 2, 4$，而陆地战士征服了节点 $5, 6$。节点 $3$ 仍未被征服。

样例 3

输入

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

输出

4 2

飞行战士征服了节点 $4, 5, 6$，而陆地战士征服了节点 $1, 2, 3$。没有未被征服的节点。

数据范围与提示

对于所有输入数据，满足 $2 \leq N \leq 200000$ 且 $2 \leq A+B \leq N$。此外，所有情况的 $N$ 值之和小于或等于 $200000$。

下面列出的限制适用于 $T$ 种情况中的每一种。