作为一名体育迷，同时也是鸽子王国的最高领导人，你正在组织一场足球比赛！总共有 $N$ 名选手报名参加比赛，你计划将他们分为三组：红队、蓝队和观众。红队和蓝队的选手人数可以不同。

在 $N$ 名参与者中存在 $M$ 对朋友关系，其中对于某个给定的常数 $K \ge 1$，满足 $M \ge 2KN$。友谊是相互的，这意味着如果 $a$ 是 $b$ 的朋友，那么 $b$ 也是 $a$ 的朋友，反之亦然。

为了让比赛更精彩，你希望确保红队的每位选手在蓝队中至少有 $K+1$ 个朋友，且蓝队的每位选手在红队中至少有 $K+1$ 个朋友。你能找到一种满足这些约束的安排吗？

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 50\,000$)，表示测试用例的数量。对于每个测试用例：

第一行包含三个整数 $N, M, K$ ($1 \le N, M, K \le 50\,000$ 且 $M \ge 2KN$)，分别表示选手人数、朋友对数和给定的常数。

接下来 $M$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u < v \le N$)，表示 $u$ 和 $v$ 是朋友。

保证在每个测试用例中，每对 $(u, v)$ 最多出现一次，且所有测试用例的 $M$ 之和不超过 $50\,000$。

输出格式

对于每个测试用例，输出两行：

第一行以一个整数 $R$ 开头，表示红队的选手人数。随后是 $R$ 个以空格分隔的整数，每个整数表示红队中一名选手的编号。

第二行格式相同。以一个整数 $B$ 开头，表示蓝队的选手人数。随后是 $B$ 个以空格分隔的整数，每个整数表示蓝队中一名选手的编号。

如果有多种方案，你可以输出其中任意一种。可以证明，在这些约束条件下，解总是存在的。

样例

样例输入 1

2
5 10 1
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
10 20 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
1 4
4 7
7 10
3 10
3 6
6 9
2 9
2 5
5 8
1 8

样例输出 1

3 2 3 4
2 1 5
3 2 8 10
2 1 9