Tráo bài 2

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
hhoangcpascal
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

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.

Input

  • 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

Output

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

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N, X \leq 10^3\).
  • Subtask \(2\) (\(30\%\) số điểm): \(N, X \leq 10^5\).
  • 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)

Example

Test 1

Input 
9 3
8 2
4 7
1 9
Output 
3

Bình luận