Mock CCC '22 Contest 1 J5 - New Year's Restrictions

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem type

Bob has made a list of N new year's resolutions, numbered from 1 to N. Upon closer inspection, however, he notices some resolutions contradict each other!

As a result, he has made a list of M restrictions, each of which is a pair (r_i, r_j) stating that if Bob fulfills the r_i-th resolution, he cannot fulfill the r_j-th resolution, and vice versa.

Wanting to have as many resolutions as possible, can you determine the maximum number of resolutions he can keep in his original list?


For this problem, you will be required to pass all the samples in order to receive any points. However, you are NOT required to pass all previous subtasks to receive points for a specific subtask.

2 \le N \le 18

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

1 \le r_i, r_j \le N

r_i \ne r_j

Each restriction will only be stated once. Note that the restriction (r_i, r_j) is the same as the restriction (r_j, r_i).

Subtask 1 [5/15]

0 \le M \le 2

Subtask 2 [7/15]

2 \le N \le 10

Subtask 3 [3/15]

No additional constraints.

Input Specification

The first line will contain 2 integers N and M.

The next M lines will contain 2 integers r_i and r_j.

Output Specification

Output one integer on one line, the maximum number of resolutions he can keep in his original list.

Sample Input

4 2
1 2
3 2

Sample Output



Bob should remove resolution 2 and keep the rest of the resolutions.


There are no comments at the moment.