#include "train.h"
#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
void dfs(int c, vb& vis, vb& aWin, vvi& adj, vi& a, vi& r) {
assert(!vis[c]);
vis[c] = true;
if(adj[c].size() == 2) {
// next and cur
if(a[c] == 1 && r[c] == 1) {
aWin[c] = true;
return;
} else if(a[c] == 0 && r[c] == 0) {
aWin[c] = false;
return;
} else {
int nex = adj[c][0] == c ? adj[c][1] : adj[c][0];
if(!vis[nex]) dfs(nex, vis, aWin, adj, a, r);
aWin[c] = aWin[nex];
return;
}
} else {
if(adj[c][0] != c) {
int nex = adj[c][0];
if(!vis[nex]) dfs(nex, vis, aWin, adj, a, r);
aWin[c] = aWin[nex];
return;
} else {
aWin[c] = r[c] == 1;
}
}
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
int n = a.size(), m=u.size();
vvi adj(n);
forR(i, m) {
adj[u[i]].push_back(v[i]);
}
vi ret(n);
vb vis(n, false), aWin(n, false);
forR(i, n) {
if(!vis[i]) {
dfs(i, vis, aWin, adj, a, r);
}
ret[i] = aWin[i] ? 1 : 0;
}
return ret;
}
