\(N\) коров (\(2 \leq N \leq 100\)) Фермера Джона, последовательно пронумерованных
\(1 \ldots N\) разработали структуру утреннего доения. Она основывается на двух
ключевых свойствах:
1. Некоторые коровы настаивают чтобы их доили раньше - в соответствии с их
социальным статусом. Например, корова 3 имеет наивысший статус, корова 3 имеет
средний статус, а корова 5 имеет низкий статус, то корову 3 нужно доить первой,
затем корову 2 и затем корову 5.
2. Некоторые коровы могут настаивать, чтобы их доили в определённой позиции
внутри порядка. Например, корова 4 может настаивать, чтобы её доили второй среди
всех коров.
По счастью, ФД всегда может подоить своих коров в порядке, удовлетворяющем
всем условиям.
К несчастью, корова 1 заболела, поэтому ФД хочет подоить эту корову как можно
раньше, чтобы раньше отпустить её в амбар отдыхать и выздоравливать. Помогите ФД
определить самую раннюю позицию, в которой можно будет подоить корову 1.
ФОРМАТ ВВОДА (файл milkorder.in):
Первая строка содержит
\(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\).
Гарантируется, что ФД может сконструировать порядок доения, удовлетворяющий
всем условиям.
ФОРМАТ ВЫВОД (файл milkorder.out):
Выведите самую раннюю позицию, на которой можно подоить корову 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3 2
4 5 6
5 3
3 1
|
4
|