#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
const int MAXN = 5005;
int n,m;
int indeg[MAXN];
vi adj[MAXN],rev[MAXN];
vi ans;
vi charging,own;
vi f(vi tot,vi sub,int type){
for(auto x:tot){
indeg[x] = rev[x].size();
if(own[x] == type) indeg[x] = 1;
}
queue<int> q;
for(auto x:sub){
indeg[x] = 0;
q.push(x);
}
while(!q.empty()){
int u = q.front();
q.pop();
for(auto v:rev[u]){
indeg[v]--;
if(!indeg[v]){
sub.pb(v);
q.push(v);
}
}
}
return sub;
}
void solve(vi gg){
// cout << gg.size() << endl;
// for(auto x:gg) cout << x << " "; cout << endl;
if(gg.empty()) return;
vi ch,win,lose,nwin,nlose;
for(auto x:gg){
if(charging[x]) ch.pb(x);
}
win = f(gg,ch,1);
if(win.size() == gg.size()){
for(auto x:gg) ans[x] = 1;
return;
}
bitset<MAXN> w;
for(auto x:win) w[x] = 1;
for(auto x:gg){
if(!w[x]) nwin.pb(x);
}
lose = f(gg,nwin,0);
w.reset();
for(auto x:lose){
w[x] = 1;
ans[x] = 0;
}
for(auto x:gg){
if(!w[x]) nlose.pb(x);
}
solve(nlose);
}
vi who_wins(vi a, vi r, vi u, vi v){
charging = r;
own = a;
n = a.size();
m = u.size();
REP(i,m){
adj[u[i]].pb(v[i]);
rev[v[i]].pb(u[i]);
}
ans.resize(n);
vi gg;
REP(i,n) gg.pb(i);
solve(gg);
return ans;
}
