## CCO '19 P5 - Marshmallow Molecules

View as PDF

Points: 15 (partial)
Time limit: 1.8s
Memory limit: 1G

Author:
Problem types
##### Canadian Computing Olympiad: 2019 Day 2, Problem 2

Hannah is building a structure made of marshmallows and skewers for her chemistry class. The structure will contain marshmallows, numbered from to . Some marshmallows will be connected by skewers. Each skewer connects two marshmallows.

Hannah has requirements for her structure. Each requirement is given as a pair , which means that there must be a skewer connecting marshmallow and marshmallow .

To ensure the stability of the structure, the following requirement must also be satisfied: if , and if there is a skewer connecting marshmallow to marshmallow , and if there is a skewer connecting marshmallow to marshmallow , then there must also be a skewer connecting marshmallow to marshmallow .

Due to austerity measures imposed by the principal's office, skewers are scarce in Hannah's school. Find the minimum number of skewers necessary to satisfy all requirements.

#### Input Specification

The first line contains two space-separated integers and .

The next lines each contain two space-separated integers, with the -th line containing and . All pairs are distinct.

For 5 of the 25 marks available, .

For an additional 5 of the 25 marks available, .

For an additional 5 of the 25 marks available, for all , there is at most one pair such that .

#### Output Specification

Output a single integer, the minimum total number of skewers.

#### Sample Input 1

6 4
1 2
1 4
4 6
4 5

#### Output for Sample Input 1

6

#### Explanation for Output for Sample Input 1

In addition to those already required, there must be skewers between the pairs of marshmallows and .

#### Sample Input 2

7 6
2 3
2 6
2 7
1 3
1 4
1 5

#### Output for Sample Input 2

16