Milking Order

题目描述

农夫约翰有 $N$ 头奶牛（$2 \leq N \leq 100$），和往常一样编号为 $1 \ldots N$。她们恰好有太多空闲时间，于是围绕农夫约翰每天早晨给她们挤奶的顺序，制定出一套复杂的社会结构。经过数周研究，农夫约翰发现该结构基于两个关键性质。

首先，由于奶牛的社会等级制度，一些奶牛坚持要在另一些奶牛之前被挤奶，这取决于每头奶牛的社会地位等级。例如，如果 3 号奶牛地位最高，2 号奶牛地位一般，5 号奶牛地位较低，那么 3 号奶牛需要最早被挤奶，然后是 2 号奶牛，最后是 5 号奶牛。

其次，一些奶牛只允许自己在挤奶顺序中的某个特定位置被挤奶。例如，4 号奶牛可能坚持要在所有奶牛中第 2 个被挤奶。

幸运的是，农夫约翰总能找到一种满足所有条件的挤奶顺序。

不幸的是，1 号奶牛最近生病了，因此农夫约翰希望尽可能早地给这头奶牛挤奶，让她能回到牛棚好好休息。请帮助农夫约翰确定：在满足所有条件的情况下，1 号奶牛在挤奶顺序中最早能出现在第几个位置。

输入格式

第一行包含 $N$, $M$（$1 \leq M < N$）和 $K$（$1 \leq K < N$），表示农夫约翰有 $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$ 个位置被挤奶。 保证在这些约束下，农夫约翰能够构造出一个合法的挤奶顺序。

输出格式

请输出 1 号奶牛在挤奶顺序中能够占据的最早位置。

6 3 2
4 5 6
5 3
3 1

4

提示

在这个例子中，农夫约翰有六头奶牛，其中 1 号奶牛生病了。他需要让 4 号奶牛在 5 号奶牛之前被挤奶，并且 5 号奶牛在 6 号奶牛之前被挤奶。此外，农夫约翰必须让 3 号奶牛第 1 个被挤奶，并且让 5 号奶牛第 3 个被挤奶。

农夫约翰必须让 3 号奶牛第 1 个被挤奶，而由于 4 号奶牛必须在 5 号奶牛之前，所以 4 号奶牛必须第 2 个被挤奶，5 号奶牛第 3 个被挤奶。因此，1 号奶牛最早只能在顺序中的第 4 个位置。

题目鸣谢：Jay Leeds

标签: USACO|2018|Bronze

来源

USACO|2018|Bronze