Арезу и ее брат Борзу получили удивительный игрушечный поезд на день рождения, и они использовали его, чтобы построить железнодорожную систему с n станциями и m односторонних путей. Каждый трек начинается на одной станции и заканчивается на той же или другой станции. На каждой станции начинается по крайней мере одна трасса.
Некоторые станции являются зарядными станциями. Всякий раз, когда поезд прибывает на зарядную станцию, он получает полную зарядку. Полностью заряженный поезд имеет достаточно энергии, чтобы путешествовать по N последовательных треков. То есть, поезд выбегает из энергии только тогда, когда он входит в (N+1)-го пути после последнего предъявления обвинения.
На каждой станции есть переключатель, который может быть направлен на любой из треков, которые начинаются на этой станции. Когда поезд находится на станции, он оставляет его с помощью дорожки, на которую указывает переключатель на этой станции.
Близнецы собираются играть в игру со своим поездом. Они уже разделили все станции между собой: каждая станция принадлежит либо Арезу, либо Борзу. Есть один поезд. В начале игры поезд на станции S и он полностью заряжен. Чтобы начать игру, владелец станции с точки переключатель на станцию один из треков, которые начинаются на станцию. Затем они поворачивают на поезд и поезд начинает путешествие вдоль дорожек.
Всякий раз, когда поезд входит в станцию в первый раз, владелец этой станции устанавливает переключатель на этой станции. Когда переключатель установлен, то он остается в том же положении для остальной части игры. Таким образом, если поезд вновь зайдет на станцию, которую он посетил ранее, он покинет эту станцию по той же трассе, что и раньше.
Так как есть конечное количество станций, поезд в конечном итоге начнет идти вдоль цикла. Цикл представляет собой последовательность различных станций с[0],С[1],⋯,с[k−1] такой, что поезд отходит станции C[я] (для 0≤i<к−1), используя тропе, идущей до станции C[я+1], и он отправляется от железнодорожного вокзала с[k−1], используя тропе, идущей до станции C[0]. Обратите внимание, что цикл может состоять из одной станции (т. е. иметь k=1), если поезд покидает станцию C[0] с помощью дорожки, которая возвращается к C[0].<br>
Арезу выигрывает игру, если поезд продолжает идти бесконечно, и Борзу выигрывает, если поезд иссякает из энергии. Другими словами, если есть хотя бы одна станция зарядки среди C[0],С[1],⋯,с[k−1], в поезде можно зарядить и цикл бесконечно, и 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. для всех 0≤I≤m−1 имеется односторонняя трасса, начинающаяся на станции u[I] и заканчивающаяся на станции v[I].
Эта процедура должна возвращать массив W длины N. Для каждого 0≤я≤N−1, значение W[я] должен быть 1, Если Arezou можете выиграть игру, которая начинается на станции я, независимо от того, как Borzou играет. В противном случае значение w [I] должно быть равно 0.
Существующие ограничения
1≤n≤5000.
n≤m≤20000.
Существует по крайней мере одна зарядная станция.
На каждой станции начинается по крайней мере одна трасса.
Там могут быть треки, которые начинаются и заканчиваются на одну и ту же станцию (т. е. U[я]=В[Я]).
Каждый трек отличается. Другими словами, нет таких двух индексов I и J ( 0≤я<с J≤м−1), Что U[я]=U[Дж] и V[я]=в[Дж].<br> 0≤u[I],v[I]≤n−1 (для всех 0≤I≤m−1).
Образец Grader считывает входные данные в следующем формате:
строка 1: nm
линия 2: а[0]А[1]...А[П−1]
строка 3: r[0]r[1]...r[n-1]
строка 4 + I (для 0≤I≤m-1): u[I]v[I]
Образец grader печатает возвращаемое значение ' who_wins‘ в следующем формате:
линия 1: ж[0]з[1]...х[п−1]