Dr. Henri is teaching a class of young students. He knows that 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 students to organize pairwise meetups among their friends. For example, if he asks a child with friends to organize gatherings, the child could organize friend to meet friend , but won't have anybody to pair friend 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.
No student will be friends with themselves, nor will any friendship be listed multiple times.
Subtask 1 [5%]
Subtask 2 [45%]
Subtask 3 [50%]
No additional constraints.
The first line contains integers and , the number of children and the number of friendships, respectively.
The next lines each contain integers and , indicating that child and are friends.
On the first line, output , the maximum number of children that can pair up their friends perfectly.
On the next line, output integers, the opinions of the children. Each integer should be either , indicating that the child prefers pineapple on pizza, or indicating that the child does not prefer pineapple on pizza.
If there are multiple configurations of opinions achieving , 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.
1 1 1 2
Children , , and each have friends after being divided by the controversy. As such, they can pair each of their friends up perfectly.
For child number , they can pair up all of their remaining friends perfectly.