题目描述

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

给定一张 $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

输入 #1

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

输出 #1

4 3

输入输出样例 #2

输入 #2

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

输出 #2

1 6

输入输出样例 #3

输入 #3

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

输出 #3

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$ 都在环上。