题目背景

译自 COI 2025 T4。

苏格拉底曰：“请告诉我，柏拉图，你是否同意：最强的斗士当属能飞之辈，如‘邦巴迪罗·鳄地罗’（Bombardiro Crocodillo）与‘邦邦比尼·古西尼’（Bombombini Gusini）？”

柏拉图对曰：“此言不当。陆地斗士，如‘嘟嘟·帕塔品’（Brr Brr Patapim）与‘瞳瞳瞳·萨胡尔’（Tung Tung Tung Sahur），虽不能飞翔，然其功业辉煌，岂可轻视？”

苏格拉底复言：“吾以为，唯有让斗士鏖战，方能识真章，待其胜负自明，方可究竟是非。”

柏拉图欣然赞曰：“善哉，苏格拉底！吾亦以为此乃探求真理之正道也。”

题目描述

本题中，「仙人掌」指的是简单连通无向图，其中每个点至多在一个环中。

给定一张 $N$ 个点 $M$ 条边的仙人掌图，点编号 $1\sim N$。给定正整数 $A,B$。

选定两个点 $s,t$（$s\neq t$）。我们将这 $N$ 个点染色：

$\gdef \dist {\operatorname{dist}}$

对于点 $i$，

• 若 $\dist(i,s)\lt \dist(i,t)$，点 $i$ 被染粉；
• 若 $\dist(i,s)\gt \dist(i,t)$，点 $i$ 被染黑；
• 否则若 $\dist(i,s)=\dist(i,t)$，点 $i$ 被染蓝。

这里，$\dist(a,b)$ 表示图中 $a,b$ 路径的最短边数。

欲使图中粉色的点有 $A$ 个，黑色的点有 $B$ 个。构造 $s,t$ 满足这个条件。数据保证有解。

输入格式

本题单个测试点内有多组测试数据。

第一行，一个正整数 $T$，表示测试数据组数。

接下来依次输入 $T$ 组数据：

第一行，四个正整数 $N,M,A,B$。

接下来 $M$ 行，每行两个正整数 $a,b$，描述图中的一条边。

数据保证有解。

输出格式

对于每组数据，输出两个正整数，表示 $s,t$。

任意一组解均可。

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

4 3

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

1 6

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

4 2

提示

数据范围

• $2\le N,\sum N\le 2\times 10^5$；
• $1\le A,B$；
• $2\le A+B\le N$；
• $a\neq b$；
• 给定的图是仙人掌。

样例解释

样例 $1$ 解释

被染粉的点：$4,5,6$。被染黑的点：$3$。

样例 $2$ 解释

被染粉的点：$1,2,4$。被染黑的点：$5,6$。

样例 $3$ 解释

被染粉的点：$4,5,6$。被染黑的点：$1,2,3$。

子任务

子任务 $0$ 为样例。

子任务编号	图的形态	$\sum N\le$	特殊性质	得分
$1$		$300$		$6$
$2$	树	$5\, 000$		$8$
$3$		$2\times 10^5$		$25$
$4$	基环树	$5\, 000$		$13$
$5$		$2\times 10^5$	$\text{A}$	$17$
$6$				$8$
$7$		$5\, 000$		$11$
$8$		$2\times 10^5$		$12$

• 特殊性质 $\text{A}$：保证存在一组解，使得 $s,t$ 都在环上。