E. Elevator Crisis
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

At the Institute of Meaningful Elevators (commonly known as IME), a student named Paim has been tasked with fixing its elevators (how ironic, I'd say). When he showed up to fix them, he found out something weird: the circuits are from out of this world! The circuit is composed of nodes that have connections, with each having a unique numerical identifier. He discovered, by reading the elevator's ancient manual, that in order for the circuit to be working, all identifiers from $$$1$$$ to $$$k$$$ can be reached by starting at node $$$1$$$ and following the connections; no identifier out of this range is reachable as well. This can be thought of as a permutation of size $$$k$$$, as, if you get all the nodes reachable from $$$1$$$, all identifiers from $$$1$$$ to $$$k$$$ will be present once.

The circuit that Paim is working with already has some connections; however, they don't necessarily respect the instructions in the manual. Given that he only has a pair of pliers to fix this issue, he's only able to remove existing connections from the circuit. Since having more nodes connected means a better functioning elevator, Paim wants to find out what's the maximum number of nodes that'll still be in use after efficiently fixing the circuit. More formally, he wants to find out what's the size of the largest subgraph, whose identifiers form a permutation. Can you help him figure this out?

This is a legitimate image from the Institute of Meaningful Elevators
Input

The first line contains two integers, $$$n$$$, $$$m$$$, $$$(1 \leq n \leq 2 \times 10^5)$$$, $$$(0 \leq m \leq \min(\frac{n \times (n - 1)}{2}, 4 \times 10^5)$$$ — the amount of nodes and the amount of connections.

The second line contains $$$n$$$ integers $$$a_i$$$, $$$(1 \leq a_i \leq 10^7)$$$ — the identifier of node $$$i$$$. It is guaranteed that each identifier is distinct and that there exists a node with the identifier $$$1$$$.

The next $$$m$$$ lines contain two integers, $$$u$$$, $$$v$$$, $$$(1 \leq u, v \leq n, u \neq v)$$$ — representing a connection. It is guaranteed that two nodes aren't connected together more than once.

Output

Print one integer, the maximum number of nodes that'll still be in use after fixing the circuit.

Example
Input
5 6
4 3 10 2 1
1 2
4 5
2 3
2 4
1 3
2 5
Output
4
Note

You can see that if you don't remove connections $$$(1, 2)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, the nodes $$$1$$$, $$$2$$$, $$$4$$$, $$$5$$$ will remain connected. Their identifiers are, respectively, $$$4$$$, $$$3$$$, $$$2$$$, $$$1$$$, which does indeed form a permutation of size $$$4$$$.