COCI '15 Contest 2 #2 Geppetto

View as PDF

Submit solution

Points: 7
Time limit: 0.6s
Memory limit: 64M

Problem types

Everyone's favorite character and puppet-maker Geppetto has opened a new pizza place, the best in town. Geppetto is trying to make the best pizza possible, but at the same time he doesn't want to have a small selection of pizzas.

He makes his pizzas out of N ingredients marked with numbers from 1 to N. All that would be simple if he could mix any ingredient with every ingredient on the pizza, but unfortunately, that is not the case. Sometimes some ingredients cannot mix and that creates additional complications for our pizza master.

There are M pairs of ingredients that cannot be on the same pizza at the same time. Given these restrictions, Geppetto wants to know how many different pizzas he can make. Help him answer this question. Two pizzas are considered different if there is an ingredient of index i that is on one pizza, but not on the other.

Input Specification

The first line of input contains two integers N and M (1 \le N \le 20, 1 \le M \le 400). Each of the following M lines contains two different numbers a, b, they represent the prohibition of mixing ingredients marked with a and b on the pizza. (1 \le a, b \le N). All pairs of ingredients are not necessarily distinct, some pair could occur multiple times.

Output Specification

The first and only line of output must contain the number of different pizzas given the restrictions in the task.

Sample Input 1

3 2
1 2
2 3

Sample Output 1


Explanation for Sample Output 1

Geppetto can make pizzas consisting of the following ingredients: \{\}, \{1\}, \{1, 3\}, \{2\}, \{3\}. Notice that a pizza can be without ingredients.

N.B. The second sample was removed for violating the problem's constraints. Specifically, it had M = 0.

Sample Input 3

3 3
1 2
1 3
2 3

Sample Output 3


Explanation for Sample Output 3

Geppetto can make a pizza that either doesn't contain any ingredients or contains only one ingredient.


  • 1
    shehar48  commented on May 12, 2019, 5:38 a.m.

    This editorial is quite misleading.

    The first line of input contains two integers N and M (1≤N≤20,1≤M≤400).

    But the input also includes M=0 and maybe includes a,b = 0.

    The author should change the input conditions.

    • 1
      Kirito  commented on May 12, 2019, 1:10 p.m.

      The test data satisfies M > 0, so the offending sample case has been removed.