19628번 - Marshmallow Molecules 다국어

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 ai 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.

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

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

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