Đồ thị điều hòa

Cho một đồ thị vô hướng đơn $G$ gồm $n$ đỉnh và $m$ cạnh. Các đỉnh được đánh số từ $1$ đến $n$.

Đồ thị được gọi là điều hòa nếu thỏa mãn tính chất sau:

• Với mọi bộ ba số nguyên $(l,m,r)$ mà $1\le l<m<r\le n$, nếu trong $G$ tồn tại đường đi từ đỉnh $l$ đến đỉnh $r$ thì cũng phải tồn tại đường đi từ đỉnh $l$ đến đỉnh $m$.

Nói cách khác, nếu từ đỉnh $l$ ta có thể đến đỉnh $r$ với $l<r$, thì ta cũng phải đến được mọi đỉnh có chỉ số nằm giữa, tức $l+1,l+2,\dots ,r-1$.

Hãy tính số cạnh ít nhất cần thêm vào $G$ để đồ thị trở nên điều hòa.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i,v_i$ ($u_i\ne v_i$) — mô tả một cạnh nối đỉnh $u_i$ với $v_i$.

Đồ thị là đơn (không có cạnh khuyên và không có hai cạnh nối cùng một cặp đỉnh).

Dữ liệu ra

In ra một số nguyên duy nhất — số cạnh tối thiểu cần thêm để đồ thị trở nên điều hòa.

Ràng buộc

• $3\le n\le 200000$
• $1\le m\le 200000$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$

Ví dụ