[USACO18OPEN] Milking Order B

Luogu
IDLGP10123
Time1000ms
Memory256MB
DifficultyP3
贪心2018USACO
Farmer John 的 $N$ 头奶牛($2\le N\le 100$),方便起见仍然编号为 $1\ldots N$,正好闲得发慌。因此,她们发展了一个与 Farmer John 每天早上为她们挤牛奶的时候的排队顺序相关的复杂的社会结构。经过若干周的研究,Farmer John 发现这个结构基于两个关键特性。 首先,由于奶牛们的社会阶层,某些奶牛会坚持要在其他奶牛之前挤奶,基于她们的社会地位等级。比方说,如果奶牛 $3$ 有最高的地位,奶牛 $2$ 位于中等地位,奶牛 $5$ 是低地位,那么奶牛 $3$ 会最早挤奶,然后是奶牛 $2$,最后是奶牛 $5$。 然后,有些奶牛只允许她们在排队顺序中一个特定的位置挤奶。比方说,奶牛 $4$ 可能坚持要在所有奶牛中的第二位挤奶。 幸运的是,Farmer John 总是能够以一种满足所有这些情况的顺序给他的奶牛们挤奶。 不幸的是,奶牛 $1$ 最近生病了,所以 Farmer John 想要尽早给这头奶牛挤奶,使得她可以回到牛棚获得急需的休息。请帮助 Farmer John 求出奶牛 $1$ 可以在挤奶顺序中出现的最早位置。 ## Input 第一行包含 $N$,$M$($1\le M<N$),和 $K$($1\le K<N$),表示 Farmer John 有 $N$ 头奶牛,其中 $M$ 头形成了社会阶层,$K$ 头需要在挤奶顺序中处于一个特定的位置。下一行包含 $M$ 个不同的整数 $m_i$($1\le m_i\le N$)。在这一行出现的奶牛必须以与她们在这行出现的顺序相同的顺序进行挤奶。下面 $K$ 行,每行包含两个整数 $c_i$($1\le c_i\le N$)和 $p_i$($1\le p_i\le N$),表示奶牛 $c_i$ 一定要在第 $p_i$ 位进行挤奶。 输入数据保证在这些限制之下,Farmer John 能够建立一个符合要求的挤奶顺序。 ## Output 输出奶牛 $1$ 可以在挤奶顺序中出现的最早位置。 [samples] ## Note 在这个例子中,Farmer John 有六头奶牛,其中奶牛 $1$ 生病了。他的挤奶顺序应该为奶牛 $4$ 在奶牛 $5$ 之前,奶牛 $5$ 在奶牛 $6$ 之前。此外,Farmer John 必须要第一个给奶牛 $3$ 挤奶,第三个给奶牛 $5$ 挤奶。 FJ 必须第一个给奶牛 $3$ 挤奶,由于奶牛 $4$ 必须要在奶牛 $5$ 之前,奶牛 $4$ 一定是第二个挤奶的,然后奶牛 $5$ 第三个。于是,奶牛 $1$ 最早在挤奶顺序中出现的位置是第四个。
Samples
Input #1
6 3 2
4 5 6
5 3
3 1
Output #1
4
API Response (JSON)
{
  "problem": {
    "name": "[USACO18OPEN] Milking Order B",
    "description": {
      "content": "Farmer John 的 $N$ 头奶牛($2\\le N\\le 100$),方便起见仍然编号为 $1\\ldots N$,正好闲得发慌。因此,她们发展了一个与 Farmer John 每天早上为她们挤牛奶的时候的排队顺序相关的复杂的社会结构。经过若干周的研究,Farmer John 发现这个结构基于两个关键特性。 首先,由于奶牛们的社会阶层,某些奶牛会坚持要在其他奶牛之前挤奶,基于她们的社会地位",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10123"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Farmer John 的 $N$ 头奶牛($2\\le N\\le 100$),方便起见仍然编号为 $1\\ldots N$,正好闲得发慌。因此,她们发展了一个与 Farmer John 每天早上为她们挤牛奶的时候的排队顺序相关的复杂的社会结构。经过若干周的研究,Farmer John 发现这个结构基于两个关键特性。\n\n首先,由于奶牛们的社会阶层,某些奶牛会坚持要在其他奶牛之前挤奶,基于她们的社会地位...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments