print2089. Нападение

printНападение

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Всем известно о существовании вампиров. Однако, никто не задумывается о непосредственной близости этих существ. В сумеречном королевстве имеется `n` городов. Между некоторыми городами есть двусторонние дороги. В каждом городе есть свой вампирский клан, в который входит `k_i` вампиров.
В свое время вампиры изгнали из королевства всех оборотней, сделав их тем самым своими лютыми врагами. Оборотням это, естественно, не понравилось. Они решили объединиться в один отряд и напасть на какой-нибудь город. Отряд, нападающий на город, содержит `w` оборотней.
Однако, приняв в рассчет то, что вампиры всегда действуют сообща, оборотни начали сомневаться в успешности их нападения. Теперь они пришли к вам за помощью. Известно, что вампиры могут перемещаться между двумя городами, соединенными дорогой, за один день. Также известно, что за один день сражения погибает `min(t,\ a,\ b)` вампиров, обороняющих осажденный город, и столько же оборотней, где `a` – текущая численность отряда вампиров, `b` – текущая численность отряда оборотней, `t` – константа. По данной вам информации, требуется узнать, смогут ли вампиры защитить город. Город считается осажденным, если существует момент времени, когда число оборотней, напавших на город, больше нуля, а число вампиров, обороняющих город, равно нулю.
В самой первой строке написано три числа: `n` (`1\ ≤\ n\ ≤\ 10^5`) – количество городов, `m` (`1\ ≤\ m\ ≤\ 10^5`) – количество дорог, `t` (`1\ ≤\ t\ ≤\ 10^3`) – количество вампиров и оборотней, погибающих за один день сражения. Во второй строке написано ровно `n` чисел: `k_i` (`1\ ≤\ k_i\ ≤\ 10^4`) – количество вампиров в `i`-м городе. Следующие `m` строк описывают дороги между городами: в каждой строке написано два числа – номера городов, соединенных дорогой. В последней строке написан номер города, на который было произведено нападение, и `w` (`1\ ≤\ w\ ≤\ 10^4`) – размер армии оборотней.
Выведите "Vampires win", если вампиры смогут отстоять свой город, и "Werewolves win" иначе.

Пример ввода 1

5 6 5
4 5 4 4 1
1 5
1 3
2 1
3 5
2 5
4 3
1 8

Пример вывода 1

Werewolves win

Пример ввода 2

5 5 1
3 1 5 1 1
1 2
1 5
1 4
4 5
2 3
1 11

Пример вывода 2

Vampires win
Обратите внимание, что в случае, если в городе погибают все вампиры, а новый отряд из соседнего города приходит на следующий день, вампиры все равно проигрывают.
Источник: neerc.ifmo.ru/school
loading