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 $N$ marshmallows, numbered from $1$ to $N$. Some marshmallows will be connected by skewers. Each skewer connects two marshmallows.

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

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

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 $N$ and $M$ $(1\le N,M\le {10}^5)$.

The next $M$ lines each contain two space-separated integers, with the $i$-th line containing $a_i$ and $b_i$ $(1\le a_i<b_i\le N)$. All $M$ pairs $(a_i,b_i)$ are distinct.

For 5 of the 25 marks available, $N\le 100$.

For an additional 5 of the 25 marks available, $N\le 5000$.

For an additional 5 of the 25 marks available, for all $1\le j\le N$, there is at most one pair $(a_i,b_i)$ such that $b_i=j$.

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 $(2,4)$ and $(5,6)$.

Sample Input 2

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

Output for Sample Input 2

16