← 返回题目列表

Codeforces · 1136/D

D. 娜斯蒂亚正在买午餐

中文机器翻译题面 查看原题

课间休息时,娜斯佳来到学校餐厅。学校有 $$$n$$$ 名学生,编号从 $$$1$$$ 到 $$$n$$$。不幸的是,娜斯佳来得太晚了,所以所有的学生都已经站在队列里了,即娜斯佳坐在队列的最后一个位置。当然,这对娜斯佳来说有点悲伤,但她不会沮丧,因为队列中的一些学生可以同意与其他学生交换位置。

形式上,存在一些对 $$$u$$$、$$$v$$$,这样如果编号为 $$$u$$$ 的学生直接站在编号为 $$$v$$$ 的学生前面,Nastya 可以询问他们,他们会改变位置。

Nastya 要求您找出她可以向前移动的队列中的最大位置数。

输入

第一行包含两个整数 $$$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$$$ 到 $$$1$$$ 的整数排列$$$n$$$)。换句话说,$$$p_i$$$ 是站在队列中第 $$$i$$$ 位置的学生的编号。

以下$$$m$$$行中的第$$$i$$$行包含两个整数$$$u_i$$$、$$$v_i$$$ ($$$1 \leq u_i, v_i \leq n, u_i \neq v_i$$$),表示编号为$$$u_i$$$的学生同意与编号为$$$u_i$$$的学生交换位置$$$v_i$$$ 如果 $$$u_i$$$ 直接位于 $$$v_i$$$ 前面。保证如果 $$$i \neq j$$$,则大于 $$$v_i \neq v_j$$$ 或 $$$u_i \neq u_j$$$。请注意,在某些配对中,两个学生可能都同意互相交换位置。

Nastya 是队列中的最后一个人,即编号为 $$$p_n$$$ 的学生。

输出

打印一个整数——队列中她可以向前移动的位置数。

示例

输入 #1

2 1
1 2
1 2

输出 #1

1

输入 #2

3 3
3 1 2
1 2
3 1
3 2

输出 #2

2

输入 #3

5 2
3 1 5 4 2
5 2
5 4

输出 #3

1

注意

在第一个示例中,Nastya 可以与队列中的第一个学生交换位置。

第二个示例中的最佳更改顺序是

- 为编号为 $$$1$$$ 和 $$$3$$$ 的学生交换位置。
- 为编号为 $$$3$$$ 和 $$$2$$$ 的学生交换位置。
- 为编号为 $$$1$$$ 和 $$$2$$$ 的学生交换位置。

在这些操作之后,队列看起来像 $$$[3, 1, 2]$$$,然后是 $$$[1, 3, 2]$$$,然后是 $$$[1, 2, 3]$$$,最后是 $$$[2, 1, 3]$$$。