#include "train.h"
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int col[MAXN],vis[MAXN],who[MAXN],mark[MAXN],n,m;
int deg[MAXN],ban[MAXN];
vector<int>adj[MAXN];
vector<int> operator - (vector<int>a,vector<int>b){
vector<int>c;
tr(it,b)mark[*it]=1;
tr(it,a)if(!mark[*it])c.pb(*it);
tr(it,b)mark[*it]=0;
return c;
}
vector<int>f(int me,vector<int>S){
for(int i=0;i<n;i++)vis[i]=deg[i]=0;
queue<int>q;
tr(it,S)q.push(*it),vis[*it]=1;
for(int i=0;i<n;i++){
if(ban[i])continue;
tr(it,adj[i])
if(!ban[*it])
deg[*it]++;
}
while(!q.empty()){
int nd=q.front();q.pop();
tr(it,adj[nd]){
if(ban[*it] or vis[*it])
continue;
if(who[*it]==me)
vis[*it]=1,q.push(*it);
else{
if(--deg[*it]==0)
vis[*it]=1,q.push(*it);
}
}
}
vector<int>res;
for(int i=0;i<n;i++)
if(!ban[i] and vis[i])
res.pb(i);
return res;
}
vector<int> who_wins(vector<int> a, vector<int> r,vector<int> u,vector<int> v) {
n=int(a.size());m=int(u.size());
for(int i=0;i<n;i++)col[i]=r[i],who[i]=a[i];
for(int i=0;i<m;i++)
adj[v[i]].pb(u[i]);
vector<int>cur,f_a,f_b;
for(int i=0;i<n;i++)
cur.pb(i);
while(!cur.empty()){
vector<int>X;
tr(it,cur)if(r[*it])X.pb(*it);
f_a=f(1,X);
f_b=f(0,cur-f_a);
if(f_b.empty())break;
cur=cur-f_b;tr(it,f_b)ban[*it]=1;
}
vector<int>ans(n,0);
tr(it,cur)ans[*it]=1;
return ans;
}
