F. Гоблины и гномы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в компьютерную игру «Гоблины и гномы». В этой игре он управляет подземным городом гномов, защищающимся от орд гоблинов.

Подземный город состоит из $$$n$$$ залов и $$$m$$$ односторонних туннелей, соединяющих некоторые пары залов. Структура туннелей такова, что, выйдя из какого-то зала, нельзя вернуться в него обратно по тоннелям.

На город готовится $$$k$$$ атак гоблинов, в $$$i$$$-й атаке город атакуют $$$i$$$ гоблинов. Цель Монокарпа — выдержать все $$$k$$$ атак.

$$$i$$$-я атака происходит следующим образом: сначала $$$i$$$ гоблинов появляются в каких-то залах города и грабят их, при этом в каждом зале появляется не более одного гоблина. После этого гоблины начинают перемещаться из зала в зал по туннелям, попутно грабя каждый зал на своем пути.

Гоблины очень жадные и хитрые, а поэтому планируют выбирать свои стартовые залы и пути так, что никакие два гоблина не пройдут через один и тот же зал. При этом, среди всех возможных планов атаки они выбирают такой, что позволяет в сумме разграбить максимальное количество залов. После того как гоблины разграбили максимальное количество залов, они покидают город.

Если в результате атаки все залы оказались разграблены — Монокарп проигрывает. Иначе гномам удается восстановить город. Если какой-то зал оказался разграблен в ходе атаки, то в ходе следующих атак он все равно представляет интерес для гоблинов (гномы успевают восстановить его).

Перед каждой атакой у Монокарпа есть время для подготовки. Монокарп может готовиться бесконечно долго (он сам решает, когда вызвать каждую атаку), но чем дольше он готовится к атаке, тем меньше очков он получает. Если Монокарп готовился к $$$i$$$-й атаке $$$t_i$$$ минут, то после нее он получает $$$\max(0, x_i - t_i \cdot y_i)$$$ очков (естественно, если он не проигрывает).

Во время подготовки к атаке Монокарп может блокировать туннели. За одну минуту он может заблокировать либо все туннели, ведущие в некоторый зал, либо все туннели, ведущие из некоторого зала. Если Монокарп заблокировал какой-то туннель во время подготовки к атаке, то этот туннель остается заблокированным и во время следующих атак.

Помогите Монокарпу выдержать все $$$k$$$ атак гоблинов и набрать максимальное количество очков!

Входные данные

В первой строке задано три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n \le 50$$$; $$$0 \le m \le \frac{n(n - 1)}{2}$$$; $$$1 \le k \le n - 1$$$) — количество залов в городе, количество туннелей, и количество атак гоблинов, соответственно.

Далее следуют $$$m$$$ строк, описывающих туннели. В $$$i$$$-й из этих строк заданы два числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$), соответствующих туннелю из зала $$$u_i$$$ в зал $$$v_i$$$. Структура туннелей такова, что, выйдя из какого-то зала, гоблин не может вернуться в него обратно по тоннелям. Между каждой парой залов существует не более одного туннеля.

Далее следуют $$$k$$$ строк, описывающих, как Монокарп получает очки за атаки. В $$$i$$$-й строке заданы два числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i \le 10^9$$$; $$$1 \le y_i \le 10^9$$$). Если Монокарп готовился к $$$i$$$-й атаке $$$t_i$$$ минут, то после нее он получает $$$\max(0, x_i - t_i \cdot y_i)$$$ очков.

Выходные данные

Выведите оптимальную последовательность действий Монокарпа в следующем формате:

В первой строке выведите целое число $$$a$$$ ($$$k \le a \le 2n + k$$$) — количество действий, которые совершает Монокарп. Во второй строке выведите сами эти действия в том порядке, в котором Монокарп их выполняет. $$$i$$$-е действие описывается целым числом $$$b_i$$$ ($$$-n \le b_i \le n$$$) в следующем формате:

  • если $$$b_i > 0$$$, то Монокарп блокирует все туннели, ведущие из зала $$$b_i$$$;
  • если $$$b_i < 0$$$, то Монокарп блокирует все туннели, ведущие в зал $$$|b_i|$$$;
  • если $$$b_i = 0$$$, то Монокарп вызывает очередную атаку гоблинов.

Нельзя повторять одно и то же действие по блокировке $$$b_i$$$ несколько раз. Каждый раз, когда Монокарп вызывает очередную атаку гоблинов, он должен выдержать ее (у гоблинов не должно быть возможности разграбить все залы города). Монокарп должен выдержать ровно $$$k$$$ атак и получить максимально возможное количество очков.

Если существует несколько оптимальных последовательностей действий — выведите любую из них.

Примеры
Входные данные
5 4 4
1 2
2 3
4 3
5 3
100 1
200 5
10 10
100 1
Выходные данные
6
-2 -3 0 0 0 0
Входные данные
5 4 4
1 2
2 3
4 3
5 3
100 100
200 5
10 10
100 1
Выходные данные
6
0 -3 0 0 1 0
Входные данные
5 10 1
1 2
1 3
1 4
1 5
5 2
5 3
5 4
4 2
4 3
2 3
100 100
Выходные данные
6
1 2 3 4 5 0
Примечание

В первом примере Монокарп сначала блокирует все туннели, ведущие в зал $$$2$$$, а потом — все туннели, ведущие в зал $$$3$$$, после чего вызывает все атаки. Он готовился к атаке $$$1$$$ две минуты, поэтому он получает за нее $$$98$$$ очков. К остальным атакам он не готовился, поэтому получает максимально возможные очки за них ($$$200$$$, $$$10$$$ и $$$100$$$). Суммарно он набирает $$$408$$$ очков.

Во втором примере Монокарп сразу вызывает первую атаку и получает за нее $$$100$$$ очков. Перед второй атакой он блокирует все туннели, ведущие в зал $$$3$$$. Это означает, что он готовится к ней одну минуту и получает $$$195$$$ очков за нее. К третьей атаке Монокарп не готовится и получает $$$10$$$ очков. Перед четвертой атакой он блокирует туннели, ведущие из зала $$$1$$$, это означает, что он готовится к атаке одну минуту и получает за нее $$$99$$$ очков. Суммарно он набирает $$$404$$$ очка.

В третьем примере Монокарпу не важно, сделает он одно действие или несколько перед единственной атакой, так как он в любом случае не получит за нее очков. А потому блокирует все туннели в городе, потратив на это целых $$$5$$$ минут и переживает атаку, не получив за нее очков.