#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define lg length()
#define pb push_back
#define INF 2000000005
#define LINF 1000000000000000005
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
#include "train.h"
int n,m;
vector <vector<int>> g, h;
int count_ones(vector<int> &a){
int ans = 0;
for(int i=0;i<n;i++){
ans += a[i];
}
return ans;
}
void f(vector<int> &s, vector<int> &w, vector<int> &a, int id){
queue<int> q;
vector<int> d(n);
for(int i=0;i<n;i++){
if(s[i]) q.push(i);
for(int j : g[i]){
if(w[j]) d[i]++;
}
}
while(sz(q)){
int i = q.front();
q.pop();
for(int j : h[i]){
if(!w[j] || s[j]) continue;
d[j]--;
if(a[j] == id || d[j] == 0){
s[j] = 1;
q.push(j);
}
}
}
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
n = sz(a);
m = sz(u);
vector<int> ans(n, 1);
for(int i=0;i<n;i++) g.pb({}), h.pb({});
for(int i=0;i<m;i++) g[u[i]].pb(v[i]), h[v[i]].pb(u[i]);
vector<int> s(n);
while(1){
for(int i=0;i<n;i++){
if(r[i] && ans[i]) s[i] = 1;
else s[i] = 0;
}
f(s, ans, a, 1);
if(count_ones(s) == count_ones(ans)) break;
for(int i=0;i<n;i++){
if(!s[i] && ans[i]) s[i] = 1;
else s[i] = 0;
}
f(s, ans, a, 0);
for(int i=0;i<n;i++){
if(s[i]) ans[i] = 0;
}
}
return ans;
}
