Comet OJ

C0709 [SDOI2019]热闹的聚会与尴尬的聚会

内存限制：256 MB 时间限制：2000 ms

题目描述

小 Q 的生日快到了，他决定周末邀请一些朋友到他的新房子一起聚会！

他的联系薄上有 $n$ 位好友，他们两两之间或者互相认识，或者互相不认识。小 Q 希望在周六办一个热闹的聚会，再在周日办一个尴尬的聚会。

一场热闹度为 $p$ 的聚会请来了任意多位好友，对于每一位到场的好友来说都有至少 $p$ 位他认识的好友也参加了聚会，且至少对于一位到场的好友来说现场恰好有 $p$ 位他认识的好友；

一场尴尬度为 $q$ 的聚会请来了恰好 $q$ 位好友，且他们两两互不认识。

两场聚会可能有重复的参与者，联系薄上也有可能有某些好友同时缺席了两场聚会。小 Q 喜欢周六聚会的热闹度 $p$ 与周日聚会的尴尬度 $q$ 之间满足：$\lfloor \frac{n}{p+1} \rfloor\le q$ 且 $\lfloor \frac{n}{q+1} \rfloor\le p$。

请帮助小 Q 找出一个可行的邀请方案。

输入格式

输入含有多组测试数据，并在第一行给定一个整数 $T$，表示总共有多少组测试数据。之后依次给出每一组数据。

每一组测试数据第一行给定两个整数 $n$ 和 $m$，依次表示联系薄中好友的总数，以及有多少对互相认识的好友。

之后 $m$ 行每行给定两个正整数 $u$ 和 $v$，满足 $1\le u\neq v\le n$，表示第 $u$ 个好友与第 $v$ 个好友互相认识。

输出

对于每一组数据输出两行，依次描述周六热闹的聚会的参加人员，与周日尴尬的聚会的参加人员列表：

第一行先输出一个正整数表示总共邀请来了多少位好友参加周六的聚会，再之后输出若干个不同的整数，按照任意顺序描述被邀请的是哪些好友。

第二行先输出一个正整数表示总共邀请来了多少位好友参加周日的聚会，再之后以任意顺序输出若干个不同的整数，同样描述了周日被邀请的好友。

如果有多组方案，你可以输出其中任何一组。

样例

样例输入 1

2
6 15
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
8 11
1 2
2 3
1 4
3 7
4 5
5 2
2 6
6 7
5 6
5 8
6 8

样例输出 1

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

提示

所有数据满足 $1\le T\le 32$ 且 $1\le m\le 10^5$。

子任务 $1$（$10$ 分）：$1\le n\le 500$；

子任务 $2$（$10$ 分）：$1\le n\le 700$；

子任务 $3$（$10$ 分）：$1\le n\le 900$；

子任务 $4$（$10$ 分）：$1\le n\le 1100$；

子任务 $5$（$10$ 分）：$1\le n\le 2000$；

子任务 $6$（$10$ 分）：$1\le n\le 3000$；

子任务 $7$（$10$ 分）：$1\le n\le 4500$；

子任务 $8$（$10$ 分）：$1\le n\le 6000$；

子任务 $9$（$10$ 分）：$1\le n\le 8000$；

子任务 $10$（$10$ 分）：$1\le n\le 10000$。

注意：本题读入量很大，请注意自己代码在读入上的所需时间。