DMOPC '20 Contest 4 P6 - Petty Children

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

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.


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

1 1 1 2


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.


  • 14
    Plasmatic  commented on May 25, 2021, 5:23 p.m. edited

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

    Just like real life 😔