Calvinball Championship, Again 2

Time limit1sMemory limit256 MB

Summary

Split n players into the fewest teams so no pair who dislike each other shares a team.

Level: Hard9 of 10
Topics: Graph, Backtracking, Brute force
Solved: No attempts yet

Problem

A Calvinball game has $n$ players. Some pairs dislike each other (symmetrically). Split everyone into teams so no disliking pair shares a team, using as few teams as possible. Output any optimal division.

Input

Line 1: $n$ and $m$ , the player count and dislike-pair count. Next $m$ lines: distinct players $a_i$ and $b_i$ who dislike each other ( $1 \leq a_i, b_i \leq n$ ).

Output

Line 1: team count $t$ . Next $t$ lines list players on each team in any order. Teams and players within a team may appear in any order.

Note

Batch data may be judged separately; the sample above is a normal stdin/stdout case.

Examples4

Example 1

Input

Expected output

Example 2
Input
```
3 3
1 2
2 3
1 3
```
Expected output
```
3
1
2
3
```
Example 3
Input
```
4 2
1 2
3 4
```
Expected output
```
2
1 3
2 4
```
Example 4
Input
```
2 1
1 2
```
Expected output
```
2
1
2
```