Nastya Is Buying Lunch
Contest: Codeforces Round 546 (Div. 2)
Difficulty rating: 1800
Tags: greedy

At the big break Nastya came to the school dining room. There are $$$n$$$ pupils in the school, numbered from $$$1$$$ to $$$n$$$. Unfortunately, Nastya came pretty late, so that all pupils had already stood in the queue, i.e. Nastya took the last place in the queue. Of course, it's a little bit sad for Nastya, but she is not going to despond because some pupils in the queue can agree to change places with some other pupils.

Formally, there are some pairs $$$u$$$, $$$v$$$ such that if the pupil with number $$$u$$$ stands directly in front of the pupil with number $$$v$$$, Nastya can ask them and they will change places.

Nastya asks you to find the maximal number of places in queue she can move forward.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 3 \cdot 10^{5}$$$, $$$0 \leq m \leq 5 \cdot 10^{5}$$$) — the number of pupils in the queue and number of pairs of pupils such that the first one agrees to change places with the second one if the first is directly in front of the second.

The second line contains $$$n$$$ integers $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$ — the initial arrangement of pupils in the queue, from the queue start to its end ($$$1 \leq p_i \leq n$$$, $$$p$$$ is a permutation of integers from $$$1$$$ to $$$n$$$). In other words, $$$p_i$$$ is the number of the pupil who stands on the $$$i$$$-th position in the queue.

The $$$i$$$-th of the following $$$m$$$ lines contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n, u_i \neq v_i$$$), denoting that the pupil with number $$$u_i$$$ agrees to change places with the pupil with number $$$v_i$$$ if $$$u_i$$$ is directly in front of $$$v_i$$$. It is guaranteed that if $$$i \neq j$$$, than $$$v_i \neq v_j$$$ or $$$u_i \neq u_j$$$. Note that it is possible that in some pairs both pupils agree to change places with each other.

Nastya is the last person in the queue, i.e. the pupil with number $$$p_n$$$.

Output format:
Print a single integer — the number of places in queue she can move forward.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example Nastya can just change places with the first pupil in the queue.

Optimal sequence of changes in the second example is

- change places for pupils with numbers $$$1$$$ and $$$3$$$.
- change places for pupils with numbers $$$3$$$ and $$$2$$$.
- change places for pupils with numbers $$$1$$$ and $$$2$$$.

The queue looks like $$$[3, 1, 2]$$$, then $$$[1, 3, 2]$$$, then $$$[1, 2, 3]$$$, and finally $$$[2, 1, 3]$$$ after these operations.

Example input:
2 1
1 2
1 2

Example output:
1

Example input:
3 3
3 1 2
1 2
3 1
3 2

Example output:
2

Editorial:
Solution 1: Let's solve the proiblem, iterating from the end, adding pupils one by one. I. e for every suffix we are solving original problem without pupils, which don't belong to this suffix. What happens when we add pupil $$$i$$$ to the suffix?
By the time when we add pupil $$$i$$$ we have answer for the previous suffix. In this answer there are, probably, pupils, which Nastya can't overtake. Let this subset of pupils be $$$P$$$. Then, if $$$i$$$-th pupil can give place for Nastya and all pupils from $$$P$$$, we will swap them. Otherwise, we can add this pupil to $$$P$$$. In order to check this condition we can iterate through pupils, who can swap with $$$i$$$-th pupil, and calculate how many are contained in $$$P$$$. This solution works in $$$O(n+m)$$$. Obviously, when we consider all suffixes, answer will be $$$n-1-|P|$$$.
Solution 2: Let's build directed graph, where $$$i$$$-th vertex corresponds $$$i$$$-th pupil and edge from $$$u$$$ to $$$v$$$ exists if and only if pupil $$$v$$$ can't give place to pupil $$$u$$$ and $$$v$$$ is closer to the beginning of queue than $$$u$$$. We can note that answer is number of vertexes in this graph, which are unreachable from Nastya's vertex. Proof:
(1) Obviously, if edge from $$$u$$$ to $$$v$$$ exists, pupil $$$v$$$ will always be in front of $$$u$$$.
(2) If vertex $$$v$$$ is reachable from vertex $$$u$$$, the same condition is true.
Let's prove that Nastya can overtake pupils, who are unreachable in graph by giving an algorithm how to do it. Let there are unreachable vertexes in front of Nastya, $$$u$$$ - the closest from them. If $$$u$$$ is directly in front of Nastya, they can swap and number of such vertexes will decrease.
Otherwise, let $$$v$$$ be the next pupil after $$$u$$$ (further from the beginning). Because $$$u$$$ is the closest unreachable vertex, $$$v$$$ is reachable. So, there is no edge from $$$u$$$ to $$$v$$$ and they can change their places. We can similarly move $$$v$$$ further and then swap him with Nastya.
Using this algorithm, Nastya can overtake all pupils, which correspond unreachable vertexes.
Fine, now we just have to calculate number of such vertexes. It can be done with standard algorithm "DFS by complement graph".