Cho một tập bài gồm ~N~ lá bài đánh số từ ~1~ tới ~N~ theo thứ tự từ trên xuống dưới. Đầu tiên người ta viết vào mỗi lá bài một số nguyên là số thứ tự lá bài đó. Xét phép tráo ~𝑆(𝑖,𝑗)~: Rút ra lá bài ghi số nguyên ~𝑖~ và chèn lên trên lá bài mang số nguyên ~𝑗~ ~(𝑖 ≠ 𝑗)~.

Ví dụ: Với ~N = 9~:

~(1,2,3,4,5,6,7,8,9) \xrightarrow[]{S(8,2)} (1,8,2,3,4,5,6,7,9) \xrightarrow[]{S(4,7)} (1,8,2,3,5,6,4,7,9) \xrightarrow[]{S(1,9)} (8,2,3,5,6,4,7,1,9)~.

Sau ~X~ phép tráo bài, người ta đánh số lại các quân bài từ ~1~ tới ~N~ theo thứ tự từ trên xuống dưới. Hãy cho biết có bao nhiêu lá bài trên đó có ghi con số lớn hơn số thứ tự của chúng.

Dữ liệu vào:

• Dòng thứ nhất chứa hai số nguyên dương ~N, X~.
• ~X~ dòng tiếp theo, dòng thứ ~k~ chứa hai số nguyên dương ~i_k~, ~j_k~ cho biết phép tráo thứ ~k~ là ~S(i_k, j_k)~ ~(i_k ≠ j_k, 1 ≤ i_k, j_k ≤ N)~.

Các số trên một dòng của Input được ghi cách nhau ít nhất một dấu cách

Kết quả: In ra một số nguyên duy nhất là kết quả tìm được.

Ràng buộc:

• Subtask ~1~ ~(30\%)~: ~N, X \leq 10^3~.
• Subtask ~2~ ~(30\%)~: ~N, X \leq 10^5~.
• Subtask ~3~ ~(40\%)~: ~N \leq 10^9~, ~X \leq 10^5~. (Tăng giới hạn so với bài gốc của thầy LMH)

Sample input:

9 3
8 2
4 7
1 9

Sample output:

3

NGUỒN: Thầy Lê Minh Hoàng