시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 1

6 4
1 2
1 4
4 6
4 5

예제 출력 1

6

In addition to those already required, there must be skewers between the pairs of marshmallows (2, 4) and (5, 6).

예제 입력 2

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

예제 출력 2

16