## COCI '15 Contest 2 #2 Geppetto

View as PDF

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 ingredients marked with numbers from to . 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 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 that is on one pizza, but not on the other.

#### Input Specification

The first line of input contains two integers and . Each of the following lines contains two different numbers , they represent the prohibition of mixing ingredients marked with and on the pizza. . 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

5

#### Explanation for Sample Output 1

Geppetto can make pizzas consisting of the following ingredients: , , , , . Notice that a pizza can be without ingredients.

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

#### Sample Input 3

3 3
1 2
1 3
2 3

#### Sample Output 3

4

#### Explanation for Sample Output 3

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

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