Dr. Henri is teaching a class of $N$ young students. He knows that $M$ of them are friends, but they have recently been divided by a controversial topic: does pineapple belong on pizza? For that reason, even if two children are friends, unless they agree on the controversial topic, they will not associate with each other and their friendship is broken.

To encourage friendships, Dr. Henri asks each of his $N$ students to organize pairwise meetups among their friends. For example, if he asks a child with $3$ friends to organize gatherings, the child could organize friend $1$ to meet friend $2$, but won't have anybody to pair friend $3$ with.

Dr. Henri can subtly change the opinion of the children. He wants to find some way to organize the opinions of the children such that the maximum number of children can pair up their friends perfectly.

Constraints

$1\le N\le 2000$

$0\le M\le \frac{N(N-1)}{2}$

No student will be friends with themselves, nor will any friendship be listed multiple times.

Subtask 1 [5%]

$1\le N\le 20$

Subtask 2 [45%]

$1\le N\le 500$

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains $2$ integers $N$ and $M$, the number of children and the number of friendships, respectively.

The next $M$ lines each contain $2$ integers $a_i$ and $b_i$, indicating that child $a_i$ and $b_i$ are friends.

Output Specification

On the first line, output $A$, the maximum number of children that can pair up their friends perfectly.

On the next line, output $N$ integers, the opinions of the $N$ children. Each integer should be either $1$, indicating that the $i^{\text{th}}$ child prefers pineapple on pizza, or $2$ indicating that the $i^{\text{th}}$ child does not prefer pineapple on pizza.

If there are multiple configurations of opinions achieving $A$, you may output any of them.

Note: your output must follow the standard convention of not having any leading or trailing whitespace, and it must end with a new line.

Sample Input

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output

4
1 1 1 2

Explanation

Children $1$, $2$, and $3$ each have $2$ friends after being divided by the controversy. As such, they can pair each of their friends up perfectly.

For child number $4$, they can pair up all of their $0$ remaining friends perfectly.