题目描述

体育迷澄正在为一个小王国筹办足球友谊赛。共有 $N$ 名选手报名参加比赛，澄需要把他们分成三类：红队、蓝队和观众。红队和蓝队的人数可以不同，也都可以不是全部选手。

在这 $N$ 名选手之间有 $M$ 对朋友关系。朋友关系是无向的，即如果 $a$ 是 $b$ 的朋友，那么 $b$ 也是 $a$ 的朋友。题目保证对给定常数 $K\ge 1$，有

为了让比赛更精彩，澄希望分队后满足：

• 红队中的每名选手，在蓝队中至少有 $K+1$ 个朋友；
• 蓝队中的每名选手，在红队中至少有 $K+1$ 个朋友。

请你构造一种满足要求的分组方案。可以证明，在本题限制下一定存在答案。

输入格式

第一行包含一个整数 $T$，表示测试用例数量。

对于每个测试用例：

第一行包含三个整数 $N,M,K$，分别表示选手数量、朋友对数和给定常数。

接下来 $M$ 行，每行包含两个整数 $u,v$，表示 $u$ 和 $v$ 是朋友。

输出格式

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

第一行先输出一个整数 $R$，表示红队人数；随后输出 $R$ 个整数，表示红队选手编号。

第二行格式相同：先输出一个整数 $B$，表示蓝队人数；随后输出 $B$ 个整数，表示蓝队选手编号。

如果存在多种答案，输出任意一种。

数据范围

• $1\le T\le 50000$；
• $1\le N,M,K\le 50000$；
• $M\ge 2KN$；
• $1\le u<v\le N$；
• 每个测试用例中，同一对 $(u,v)$ 最多出现一次；
• 所有测试用例的 $M$ 之和不超过 $50000$。

样例 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

输出

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