{"code":"shuffle2","name":"Tráo bài 2","description":"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 $𝑗$ $(𝑖 ≠ 𝑗)$.\r\n\r\nVí dụ: Với $N = 9$:\r\n\r\n$(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)$.\r\n\r\nSau $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ó\r\nbao nhiêu lá bài trên đó có ghi con số lớn hơn số thứ tự của chúng.\r\n\r\n#### Input\r\n+ Dòng thứ nhất chứa hai số nguyên dương $N, X$.\r\n+ $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)$.\r\n\r\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*\r\n\r\n#### Output\r\n- In ra một số nguyên duy nhất là kết quả tìm được.\r\n\r\n#### Scoring\r\n+ Subtask $1$ ($30\\%$ số điểm): $N, X \\leq 10^3$.\r\n+ Subtask $2$ ($30\\%$ số điểm): $N, X \\leq 10^5$.\r\n+ Subtask $3$ ($40\\%$ số điểm): $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)**\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        9 3\r\n        8 2\r\n        4 7\r\n        1 9 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        3\r\n        ```","points":300.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}