Description

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

给定一张 $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$ 满足这个条件。数据保证有解。

Input Format

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

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

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

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

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

数据保证有解。

Output Format

对于每组数据，输出两个正整数，表示 $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

Hint

数据范围

• $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$ 为样例。

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