CS
Problems Base course RU

Problem

Exam days

graph dynamic programming bit tricks scheduling

An exam session has n exams. Some pairs of exams cannot be held on the same day: they have students in common. Any number of exams can be held on one day, as long as no two of them clash. In how many days can the whole session be held?

In one of the tests the exams are replaced by the twenty most mentioned roles of War and Peace from the article on graph colouring: two roles clash if the characters meet in one chapter, and the answer is how many actors are needed.

Input

The first line holds the number of exams n and the number of clashing pairs m (1 ≤ n ≤ 20, 0 ≤ m ≤ n(n − 1)/2). Then come m lines a b: exams a and b cannot be on the same day (1 ≤ a, b ≤ n, a ≠ b, pairs do not repeat).

Output

One number: the smallest number of days.

Examples

Example 1

Input
5 5
1 2
1 5
2 3
3 4
4 5
Output
3

Example 2

Input
9 13
1 2
1 5
2 5
2 7
3 5
4 5
4 8
4 9
6 7
6 8
7 8
7 9
8 9
Output
3

Limits

Time · Python
8000 ms
Time · Go
2000 ms
Memory
256 MB
Judging
13 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

If some q exams clash pairwise, at least q days are needed. Maybe the answer is the largest such group? Check it on the first example: five exams in a cycle.

2Hint 2

The greedy methods from the article, even DSatur, do not guarantee the answer: on the second example DSatur takes four days, while three are enough. An exact method is needed, and there are only twenty exams. How many subsets of exams are there in all? And what if instead of looking for a timetable you count how many there are?

3The idea

A day is an independent set of exams: no two clash. A session in k days is k independent sets that together cover all the exams: if some exam falls into several, leave it in the first. So the answer is the smallest k for which the number of such collections is positive. And the number of collections is computed by the inclusion–exclusion formula through one number for each subset of exams.

4Walkthrough

Let V be all the exams and i(S) the number of independent subsets of the set S, the empty one included.

The number of ordered collections (I1, …, Ik) of independent sets that together cover V equals

$$a_k = \sum_{S \subseteq V} (-1)^{|V \setminus S|}\, i(S)^k.$$

i(S)k is the number of collections of k independent sets that all lie inside S. Take some collection, and let U be the union of its sets. It is counted in the term of every S containing U, with the sign (−1)|V ∖ S|. Such S are obtained from V by throwing out any subset T of V ∖ U, and the sum of the signs is ΣT (−1)|T| = (1 − 1)|V ∖ U|. This is zero if U ≠ V, and one if the collection covers everything. So each covering collection is counted exactly once, and the others zero times.

The numbers i(S) for all 2n subsets are computed with one addition each. Take the exam v with the smallest number in S. The independent subsets of S without v are i(S ∖ {v}), and those with v are the ones without its neighbours: i(S ∖ {v} ∖ neighbours(v)). Subsets and neighbours are conveniently stored as bit masks, as in DP over masks: “S without v” is S ^ low, where low = S & -S.

Then for k = 1, 2, … compute ak and stop at the first non-zero one. The numbers are huge, i(S) reaches 220 and the power goes up to the twentieth, so compute modulo two large primes. While k is less than the answer, ak is exactly zero, and zero modulo anything too. At the answer ak is positive, and zero modulo both primes could only come out if it were divisible by their product; that does not happen on the tests, which has been checked by exact search. In Python the powers for all million subsets at once are conveniently kept in a numpy array: the product of two numbers less than 109 fits in int64.

4+Solution
5Complexity

O(2n·n) time and O(2n) memory: a million subsets and up to twenty powers. This method was proposed by Andreas Björklund, Thore Husfeldt and Mikko Koivisto in 2006; before them the best exact algorithms went over subsets of subsets and needed about 2.4n steps.

The backtracking from the article, DSatur trying another colour at a dead end, also makes it in time on these tests, but it has no guarantee: there are graphs on which it goes through exponentially many colourings before proving that fewer is impossible.

6Common mistakes
  • The largest clique. A lower bound, but not the answer. Five exams in a cycle contain no three pairwise clashing ones, yet three days are needed. The Grötzsch graph of the third test has not even triangles, yet four days are needed.
  • DSatur without backtracking. This is wrong.py: on the second example it puts the exams on four days.
  • Powers without a modulus. i(S)k does not fit in any built-in type. In Python big integers keep it correct but not fast: a million long numbers for each k is already a lot.
  • The signs. The sign of a term depends on how many exams are thrown out, not how many are kept: (−1)n − |S|.

Algorithms behind it

GRA Algorithm Graph colouring Different colours for neighbours: the greedy way, the smallest-last order, DSatur and exact search on maps and timetables. O(V + E) for greedy in a given order and smallest last; O((V + E) log V) for DSatur with a heap 2 problems DP Technique Bitmask DP The state is a subset written in the bits of a number: an exact travelling salesman, assignments, tilings by profile. O(2ⁿ · n²) for the travelling salesman 2 problems
The algorithms catalogue