Marshmallow Molecules

시간 제한4초메모리 제한512 MB

요약

필수 간선들이 주어질 때, a<b<c이고 (a,b)와 (a,c)가 있으면 (b,c)도 있어야 한다는 조건을 만족하도록 추가할 최소 간선 수를 구한다.

난이도: 보통10점 중 7점
유형: 유니온 파인드, 그래프, 조합론
정답자: 아직 제출이 없습니다

문제

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 (ai, bi), which means that there must be a skewer connecting marshmallow ai and marshmallow bi.

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.

입력

The first line contains two space-separated integers N and M (1 ≤ N, M ≤ 105).

The next M lines each contain two space-separated integers, with the i-th line containing ai and bi (1 ≤ ai < bi ≤ N). All M pairs (ai, bi) are distinct.

출력

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

예제2

예제 1
입력
```
6 4
1 2
1 4
4 6
4 5
```
예상 출력
```
6
```
예제 2
입력
```
7 6
2 3
2 6
2 7
1 3
1 4
1 5
```
예상 출력
```
16
```