#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include "train.h"
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll)a; i<(ll)b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 100000000000000000LL
ll insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
class DiGraph
{
public:
ll N;
vector<vector<ll> > adj;
vector<bool> visited;
vector<ll> current; //for CC
vector<bool> c; //for Bip
bool bip; //for Bip
vector<ll> TS;//Top Sort
vector<ll> SCC; //Attributes a number to each node
vector<vector<ll> > adjK; //reverse graph, for Kosaraju
DiGraph(vector<vector<ll> > ad)
{
adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false); c.pb(-1); SCC.pb(-1LL);}
vector<ll> xx; REP(i,0,N) {adjK.pb(xx);}
REP(i,0,adj.size())
{
REP(j,0,adj[i].size()) {adjK[adj[i][j]].pb(i);}
}
}
void Reset()
{
REP(i,0,N) {visited[i]=false;}
current.clear();
}
void DFS(ll s)
{
if(visited[s]) {return;}
visited[s]=true;
REP(i,0,adj[s].size())
{
if(!visited[adj[s][i]]) {c[adj[s][i]]=(c[s]+1)%2; DFS(adj[s][i]);}
else if(c[adj[s][i]]==c[s]) {bip=false;}
}
current.pb(s); //only needed for Kosaraju
return;
}
vector<ll> BFS(ll s)
{
vector<ll> distance; REP(i,0,N) {distance.pb(INF);}
REP(i,0,N) {visited[i]=false;}
distance[s]=0; visited[s]=true;
deque<ll> d; d.pb(s); ll cur;
while(!d.empty())
{
cur=d.front(); d.pop_front();
REP(i,0,adj[cur].size())
{
if(!visited[adj[cur][i]])
{
visited[adj[cur][i]]=true;
d.pb(adj[cur][i]);
distance[adj[cur][i]]=distance[cur]+1;
}
}
}
return distance;
}
bool Bip()
{
c[0]=0;
bip=true;
DFS(0);
if(bip) {return true;}
else {return false;}
}
void DFSTS(ll s)
{
REP(i,0,adj[s].size())
{
if(!visited[adj[s][i]]) {DFSTS(adj[s][i]);}
}
visited[s]=true; TS.pb(s);
}
void TopSort()
{
Reset();
REP(i,0,N)
{
if(visited[i]) {continue;}
DFSTS(i);
}
reverse(TS.begin(),TS.end());
}
void DFSK(ll s)
{
if(visited[s]) {return;}
visited[s]=true;
REP(i,0,adjK[s].size())
{
if(!visited[adjK[s][i]]) {DFSK(adjK[s][i]);}
}
current.pb(s); //only needed for Kosaraju
return;
}
void Kosaraju()
{
if(SCC[0]!=-1) {return;}
Reset();
REP(i,0,N)
{
if(visited[i]) {continue;}
DFS(i);
}
vector<ll> List=current;
Reset();
ll c=0LL;
for(ll i=N-1LL;i>=0LL;i--)
{
ll node=List[i];
if(visited[node]) {continue;}
DFSK(node);
REP(j,0,current.size()) {SCC[current[j]]=c;}
c++;
current.clear();
}
}
DiGraph SCCGraph()
{
Kosaraju();
set<pl> ed;
REP(i,0,adj.size())
{
REP(j,0,adj[i].size())
{
ed.insert(mp(SCC[i],SCC[adj[i][j]]));
}
}
vector<vector<ll> > a; vector<ll> xx;
ll nscc=-INF; REP(i,0,N) {nscc=max(nscc,SCC[i]+1LL);}
REP(i,0,nscc) {a.pb(xx);}
set<pl>::iterator it=ed.begin();
pl cur;
while(it!=ed.end())
{
cur=*it;
if(cur.ff!=cur.ss) {a[cur.ff].pb(cur.ss);}
it++;
}
DiGraph ans(a);
return ans;
}
};
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
ll N=a.size(); ll M=u.size();
vector<vector<ll> > adj; vector<ll> xx; REP(i,0,N) {adj.pb(xx);}
REP(i,0,M)
{
adj[u[i]].pb(v[i]);
}
DiGraph G(adj);
vector<int> ans; REP(i,0,N) {ans.pb(0);}
REP(s,0,N)
{
ll cur=s;
while(1>0)
{
if(find(adj[cur].begin(),adj[cur].end(),cur)==adj[cur].end()) {cur++;continue;}
if(r[cur]==1 && a[cur]==1) {ans[s]=1; break;}
else if(r[cur]==0 && a[cur]==0) {ans[s]=0;break;}
if(adj[cur].size()==1 && r[cur]==1) {ans[s]=1;break;}
cur++;
}
}
return ans;
}
