#include "train.h"
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> g, rg;
vector<int> a, r, in;
void solve(vector<int>& v, int p){
vector<int> deg(n, 0);
for (int i=0; i<n; i++){
for (int next : g[i]) deg[i] += in[next];
}
queue<int> q;
for (int i=0; i<n; i++){
if (v[i]) q.push(i);
}
while (!q.empty()){
int cur = q.front();
q.pop();
for (int next : rg[cur]){
if (!in[next]) continue;
if (v[next]) continue;
deg[next]--;
if (a[next] == p || deg[next] == 0){
v[next] = 1;
q.push(next);
}
}
}
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v){
n = a.size();
m = u.size();
::r = r;
::a = a;
g.resize(n);
rg.resize(n);
for (int i=0; i<m; i++){
rg[v[i]].push_back(u[i]);
g[u[i]].push_back(v[i]);
}
in.resize(n, 1);
while (true){
vector<int> v(n, 0);
for (int i=0; i<n; i++) v[i] = (in[i] && r[i]);
solve(v, 1);
vector<int> v2(n, 0);
for (int i=0; i<n; i++) v2[i] = (in[i] && !v[i]);
solve(v2, 0);
bool done = true;
for (int i=0; i<n; i++){
if (!v2[i]) continue;
done = false;
in[i] = 0;
}
if (done) return v;
}
}
