Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

D. Настя идет в столовую
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На перемене Настя пришла в школьную столовую. Всего в школе $$$n$$$ человек, пронумерованных от $$$1$$$ до $$$n$$$. К сожалению, Настя задержалась на уроках, поэтому стоит последней в очереди. Конечно, в столовой образовалась большая очередь, однако Настя не унывает, так как некоторые люди в очереди готовы пропускать каких-то других людей.

Формально, есть сколько-то пар $$$u$$$, $$$v$$$ таких, что если человек с номером $$$u$$$ стоит непосредственно перед человеком с номером $$$v$$$, то Настя может попросить их, и они поменяются местами. Так как людей очень много, Настя просит вас сказать, как близко к началу она сможет продвинуться.

Формально, она просит вас сказать максимальное количество мест в очереди, на которое она может продвинуться.

Входные данные

В первой строке вводится два целых числа $$$n$$$, $$$m$$$, разделенных пробелом ($$$1 \leq n \leq 3 \cdot 10^{5}$$$, $$$0 \leq m \leq 5 \cdot 10^{5}$$$) — количество людей в очереди и количество пар людей, в которых первый человек может пропустить второго, если первый стоит непосредственно перед вторым.

В следующей строке вводятся $$$n$$$ различных целых чисел $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$ — изначальное положение людей в очереди от начала к концу ($$$1 \leq p_i \leq n$$$, $$$p$$$ — перестановка чисел от $$$1$$$ до $$$n$$$). Иными словами, $$$p_i$$$ — номер человека, стоящего $$$i$$$-м в очереди.

В $$$i$$$-й из следующих $$$m$$$ строк вводятся два целых числа $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n, u_i \neq v_i$$$), обозначающие, что человек с номером $$$u_i$$$ готов пропустить человека с номером $$$v_i$$$, если $$$u_i$$$ стоит прямо перед человеком $$$v_i$$$ в очереди. Гарантируется, что если $$$i \neq j$$$, то $$$v_i \neq v_j$$$, либо $$$u_i \neq u_j$$$. Заметьте, что в одной паре людей возможно такое, что оба готовы пропустить друг друга.

Настя — последний человек в очереди (то есть человек с номером $$$p_n$$$).

Выходные данные

Выведите одно целое число — максимальное количество мест в очереди, на которое она может продвинуться.

Примеры
Входные данные
2 1
1 2
1 2
Выходные данные
1
Входные данные
3 3
3 1 2
1 2
3 1
3 2
Выходные данные
2
Входные данные
5 2
3 1 5 4 2
5 2
5 4
Выходные данные
1
Примечание

В первом примере Настя просто может поменяться местами с первым человеком в очереди.

Во втором примере можно, чтобы сначала поменялись местами школьники с номерами $$$1$$$ и $$$3$$$, потом $$$3$$$ и $$$2$$$, потом $$$1$$$ и $$$2$$$. Очередь будет выглядеть как $$$[3, 1, 2]$$$, затем $$$[1, 3, 2]$$$, затем $$$[1, 2, 3]$$$ и наконец $$$[2, 1, 3]$$$.