USACO 2018 US Open Contest, Bronze

Problem 2. Milking Order


Contest has ended.

Log in to allow submissions in analysis mode


Farmer John的$N$头奶牛（$2 \leq N \leq 100$），方便起见仍然编号为$1 \ldots N$，正好闲得发慌。因此，她们发展了一个与Farmer John每天早上为她们挤牛奶的时候的排队顺序相关的复杂的社会结构。经过若干周的研究，Farmer John发现这个结构基于两个关键特性。

首先，由于奶牛们的社会阶层，某些奶牛会坚持要在其他奶牛之前挤奶，基于她们的社会地位等级。比方说，如果奶牛3有最高的地位，奶牛2位于中等地位，奶牛5是低地位，那么奶牛3会最早挤奶，然后是奶牛2，最后是奶牛5。

然后，有些奶牛只允许她们在排队顺序中一个特定的位置挤奶。比方说，奶牛4可能坚持要在所有奶牛中的第二位挤奶。

幸运的是，Farmer John总是能够以一种满足所有这些情况的顺序给他的奶牛们挤奶。

不幸的是，奶牛1最近生病了，所以Farmer John想要尽早给这头奶牛挤奶，使得她可以回到牛棚获得急需的休息。请帮助Farmer John求出奶牛1可以在挤奶顺序中出现的最早位置。

输入格式（文件名：milkorder.in）：

第一行包含$N$，$M$（$1 \leq M < N$），和$K$（$1 \leq K < N$），表示Farmer John有$N$头奶牛，其中$M$头形成了社会阶层，$K$头需要在挤奶顺序中处于一个特定的位置。下一行包含$M$个不同的整数$m_i$（$1 \leq m_i \leq N$）。在这一行出现的奶牛必须以与她们在这行出现的顺序相同的顺序进行挤奶。下面$K$行，每行包含两个整数$c_i$（$1 \leq c_i \leq N$）和$p_i$（$1 \leq p_i \leq N$），表示奶牛$c_i$一定要在第$p_i$位进行挤奶。

输入数据保证在这些限制之下，Farmer John能够建立一个符合要求的挤奶顺序。

输出格式（文件名：milkorder.out）：

输出奶牛1可以在挤奶顺序中出现的最早位置。

输入样例：

6 3 2
4 5 6
5 3
3 1

输出样例：

4

在这个例子中，Farmer John有六头奶牛，其中奶牛1生病了。他的挤奶顺序应该为奶牛4在奶牛5之前，奶牛5在奶牛6之前。此外，Farmer John必须要第一个给奶牛3挤奶，第三个给奶牛5挤奶。

FJ必须第一个给奶牛3挤奶，由于奶牛4必须要在奶牛5之前，奶牛4一定是第二个挤奶的，然后奶牛5第三个。于是，奶牛1最早在挤奶顺序中出现的位置是第四个。

供题：Jay Leeds

Contest has ended. No further submissions allowed.