Арезу и ее брат Борзу получили изумительный игрушечный поезд на денек

Арезу и ее брат Борзу получили дивный игрушечный поезд на денек рождения, и они использовали его, чтоб построить железнодорожную систему с n станциями и m однобоких путей. Каждый трек начинается на одной станции и заканчивается на той же либо другой станции. На каждой станции начинается по крайней мере одна трасса.

Некие станции являются зарядными станциями. Всякий раз, когда поезд прибывает на зарядную станцию, он получает полную зарядку. Вполне заряженный поезд имеет достаточно энергии, чтобы странствовать по N последовательных треков. То есть, поезд выбегает из энергии только тогда, когда он входит в (N+1)-го пути после заключительного предъявления порицания.

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

Близнецы собираются играть в игру со своим поездом. Они теснее разделили все станции меж собой: любая станция принадлежит или Арезу, или Борзу. Есть один поезд. В начале забавы поезд на станции S и он на сто процентов заряжен. Чтоб начать игру, владелец станции с точки переключатель на станцию один из треков, которые начинаются на станцию. Потом они поворачивают на поезд и поезд начинает странствие вдоль дорожек.

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

Так как есть окончательное количество станций, поезд в окончательном итоге начнет идти вдоль цикла. Цикл представляет собой последовательность различных станций с[0],С[1],,с[k1] таковой, что поезд отходит станции C[я] (для 0ilt;к1), используя тропе, идущей до станции C[я+1], и он отчаливает от железнодорожного вокзала с[k1], используя тропе, идущей до станции C[0]. Обратите внимание, что цикл может состоять из одной станции (т. е. иметь k=1), если поезд покидает станцию C[0] с помощью дорожки, которая ворачивается к C[0].

Арезу выигрывает игру, если поезд продолжает идти неисчерпаемо, и Борзу выигрывает, если поезд иссякает из энергии. Другими словами, если есть хотя бы одна станция зарядки посреди C[0],С[1],,с[k1], в поезде можно зарядить и цикл нескончаемо, и Arezou выигрывает. По другому у него закончится энергия (возможно, после поворота цикла несколько раз), и Борзов одолеет.

Для вас дается описание жд системы. Arezou и Borzou собираетесь играть в забавы н. В s-й забаве, для 0хн1, поезд будет на станции с. Ваша задачка-отыскать для каждой забавы, есть ли стратегия для Arezou гарантии, что она выиграет, самостоятельно от того, как Borzou играет.

Деталь реализации

Необходимо выполнить последующую функцию:
инт[] who_wins(Тип int[] а, инт[] р, инт[] у, инт[] в)

ответ: массив длины N. Если Arezou обладает станции я, [Я]=1. В неприятном случае, Borzou обладает станцией I и[я]=0.
r: массив длины n. Если станция I является зарядной станцией, r[I]=1. В неприятном случае r[I]=0.
u и v: массивы длины m. для всех 0Im1 имеется односторонняя трасса, возникающая на станции u[I] и кончающаяся на станции v[I].
Эта процедура должна отдавать массив W длины N. Для каждого 0яN1, значение W[я] обязан быть 1, Если Arezou можете выиграть забаву, которая начинается на станции я, независимо от того, как Borzou играет. В неприятном случае значение w [I] должно быть одинаково 0.
Существующие ограничения

1n5000.
nm20000.
Существует по последней мере одна зарядная станция.
На каждой станции начинается по последней мере одна трасса.
Там могут быть треки, которые начинаются и заканчиваются на одну и ту же станцию (т. е. U[я]=В[Я]).
Каждый трек отличается. Иными словами, нет таких 2-ух индексов I и J ( 0яlt;с Jм1), Что U[я]=U[Дж] и V[я]=в[Дж].
0u[I],v[I]n1 (для всех 0Im1).
Эталон Grader считывает входные данные в последующем формате:

строчка 1: nm
линия 2: а[0]А[1]...А[П1]
строка 3: r[0]r[1]...r[n-1]
строчка 4 + I (для 0Im-1): u[I]v[I]

Эталон grader печатает отдаваемое значение ' who_wins в следующем формате:

линия 1: ж[0]з[1]...х[п1]