Nastya và Hàng Ăn Trưa

Điểm: 6,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Có $N$ học sinh đang đứng trong một hàng đợi, được đánh số từ $1$ đến $N$ . Vị trí ban đầu trong hàng được mô tả bởi hoán vị $p_{1}, p_{2}, \dots, p_{N}$ , trong đó $p_{i}$ là số hiệu của học sinh đứng ở vị trí thứ $i$ (vị trí $1$ là đầu hàng, vị trí $N$ là cuối hàng).

Nastya là học sinh đứng ở cuối hàng, tức là học sinh có số hiệu $p_{N}$ .

Cho $M$ cặp $(u, v)$ với ý nghĩa: nếu học sinh $u$ đang đứng ngay trước học sinh $v$ trong hàng, thì $u$ đồng ý đổi chỗ cho $v$ (sau khi đổi, $v$ tiến lên một vị trí và $u$ lùi xuống một vị trí).

Hãy tính số vị trí tối đa mà Nastya có thể tiến lên trong hàng nhờ chuỗi các lượt đổi chỗ liên tiếp (mỗi lượt sử dụng một cặp $(u, v)$ thỏa mãn, không nhất thiết khác nhau giữa các lượt).

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $M$ .
Dòng thứ hai chứa $N$ số nguyên $p_{1}, p_{2}, \dots, p_{N}$ — hoán vị mô tả hàng đợi ban đầu.
$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_{i}, v_{i}$ ( $u_{i} \neq v_{i}$ ) — một cặp đồng ý đổi chỗ. Các cặp $(u_{i}, v_{i})$ đôi một phân biệt; tuy nhiên có thể đồng thời tồn tại cả $(a, b)$ lẫn $(b, a)$ .

Dữ liệu ra

In ra một số nguyên duy nhất — số vị trí tối đa Nastya có thể tiến lên.

Ràng buộc

$1 \leq N \leq 3 \cdot 10^{5}$
$0 \leq M \leq 5 \cdot 10^{5}$
$1 \leq p_{i} \leq N$ và $p$ là một hoán vị của $1, 2, \dots, N$
$1 \leq u_{i}, v_{i} \leq N$

Ví dụ

Input	Output	Giải thích
5 2 3 1 5 4 2 5 2 5 4	1	Hàng đầu là $[3, 1, 5, 4, 2]$ . Nastya là số $2$ . Cặp $(5, 2)$ cho phép $5$ và $2$ đổi chỗ khi $5$ đứng ngay trước $2$ , nhưng $4$ đang chen giữa. Trước hết áp dụng cặp $(5, 4)$ để được $[3, 1, 4, 5, 2]$ , rồi áp dụng cặp $(5, 2)$ được $[3, 1, 4, 2, 5]$ . Nastya tiến lên $1$ vị trí.
3 3 3 1 2 1 2 3 1 3 2	2	Lần lượt: đổi $(3, 1)$ → $[1, 3, 2]$ , đổi $(3, 2)$ → $[1, 2, 3]$ , đổi $(1, 2)$ → $[2, 1, 3]$ . Nastya (số $2$ ) tiến từ vị trí $3$ lên vị trí $1$ , tăng $2$ bậc.
2 1 1 2 1 2	1	Học sinh $1$ và $2$ đổi chỗ trực tiếp, Nastya tiến lên đầu hàng.

Bình luận

Không có bình luận tại thời điểm này.