This is an answer-submission problem.

There are $n$ people on a playground. Little P wants to divide these people into the minimum possible number of teams. However, there are $m$ pairs of people who have conflicts with each other, so we cannot place people who have a conflict into the same team.

Little P is seeking your help. You are expected to divide everyone into the minimum possible number of teams and provide the corresponding output for each input file.

Input

This is an answer-submission problem with 10 input datasets, named 1.in ~ 10.in.

The format of each input file is as follows:

The first line contains two positive integers $n$ and $m$, representing the total number of people and the number of conflicting pairs, respectively.

The next $m$ lines each contain two positive integers $a_i$ and $b_i$, where $1 \le a_i, b_i \le n$, indicating that there is a conflict between $a_i$ and $b_i$.

Output

For each input dataset, you need to submit the corresponding output file 1.out ~ 10.out.

For each input file, output any valid solution that uses the minimum number of teams.

The format of each submission file is as follows:

The first line contains the number of teams $t$.

The next $t$ lines each contain several positive integers representing the members of the $i$-th team.

Examples

Input 1

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

Output 1

3
6
4 3
1 2 5

Note

This is one possible valid solution.

Subtasks

Each test case is worth 10 points.