Description

There are $n$ friends in his contact list. Any two friends either know each other or do not know each other. Xiao Q wants to hold a lively party on Saturday, and then an awkward party on Sunday.

• A party with liveliness $p$ invites any number of friends. For every friend who attends, there are at least $p$ friends that he knows also attending the party, and for at least one attending friend, there are exactly $p$ friends that he knows at the party.
• A party with awkwardness $q$ invites exactly $q$ friends, and they are pairwise not acquainted with each other.

The two parties may have overlapping participants, and it is also possible that some friends in the contact list miss both parties.

Xiao Q likes the liveliness $p$ of Saturday’s party and the awkwardness $q$ of Sunday’s party to satisfy: $\left\lfloor \frac{n}{p+1} \right\rfloor\! \le q$ and $\left\lfloor \frac{n}{q+1} \right\rfloor\! \le p$.

Please help Xiao Q find a feasible invitation plan.

Input Format

The input contains multiple test cases. The first line gives an integer $T$, which denotes the number of test cases. Then each test case follows.

For each test case, the first line gives two integers $n$ and $m$, which denote the total number of friends in the contact list, and the number of pairs of friends who know each other.

Then $m$ lines follow. Each line gives two positive integers $u$ and $v$, satisfying $1\le u\neq v\le n$, meaning that friend $u$ and friend $v$ know each other.

Output Format

For each test case, output two lines, describing the participant list of Saturday’s lively party and Sunday’s awkward party, respectively.

The first line first outputs a positive integer, indicating how many friends are invited to the Saturday party, and then outputs several distinct integers in any order, describing which friends are invited.

The second line first outputs a positive integer, indicating how many friends are invited to the Sunday party, and then outputs several distinct integers in any order, also describing which friends are invited on Sunday.

If there are multiple valid solutions, you may output any one of them.

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

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

Hint

Constraints

• Subtask $1$ ($10$ points): $1\le n\le 500$.
• Subtask $2$ ($10$ points): $1\le n\le 700$.
• Subtask $3$ ($10$ points): $1\le n\le 900$.
• Subtask $4$ ($10$ points): $1\le n\le 1.1 \times {10}^3$.
• Subtask $5$ ($10$ points): $1\le n\le 2 \times {10}^3$.
• Subtask $6$ ($10$ points): $1\le n\le 3 \times {10}^3$.
• Subtask $7$ ($10$ points): $1\le n\le 4.5 \times {10}^3$.
• Subtask $8$ ($10$ points): $1\le n\le 6 \times {10}^3$.
• Subtask $9$ ($10$ points): $1\le n\le 8 \times {10}^3$.
• Subtask $10$ ($10$ points): $1\le n\le {10}^4$.

For all test points, it holds that $1\le T\le 32$ and $1\le m\le 10^5$.

Notes

The input size of this problem is very large. Please pay attention to the time needed for input in your code.

Explanation

Thanks to @81179332_ for providing the spj!

Translated by ChatGPT 5