P12403 [COI 2025] 象掌兽 / Lirili Larila

译自 [COI 2025](https://hsin.hr/hio2025/) 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$。 任意一组解均可。

## 数据范围 - $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$ | 基环树 | $2\times 10^5$ | | $8$ | | $7$ | | $5\, 000$ | | $11$ | | $8$ | | $2\times 10^5$ | | $12$ | - 特殊性质 $\text{A}$：保证存在一组解，使得 $s,t$ 都在环上。