#include "train.h"
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <cassert>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define INF (1LL<<60)
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;
int N, M;
vector<int> G[5000], R[5000];
bool self[5000];
bool used[5000];
int ord[5000];
vector<int> W[5000];
void dfs(int x,vector<int> &ret) {
if (used[x])return;
used[x]=true;
for (int t : G[x]) dfs(t, ret);
ret.pb(x);
}
void dfs2(int x,int k){
if (used[x])return;
used[x]=true;
ord[x]=k;
for (int t : R[x]) dfs2(t, k);
}
vector<int> G2[5000];
bool earn[5000];
int memo[5000];
int dfs3(int x) {
if (memo[x] != -1) return memo[x];
int ret = earn[x];
for (int t : G2[x]) ret |= dfs3(t);
return memo[x] = ret;
}
vector<int> who_wins(vector<int> owner, vector<int> color, vector<int> U, vector<int> V) {
N = owner.size(), M = U.size();
bool case1 = true;
rep(i, M) {
G[U[i]].pb(V[i]);
R[V[i]].pb(U[i]);
if (!(V[i] == U[i] || V[i] == U[i]+1)) case1 = false;
}
bool allA = true, allB = true;
for (int x : owner) if (x != 1) allA = false;
for (int x : owner) if (x != 0) allB = false;
if (false){
//if (case1) {
vector<int> win(N);
for (int x=N-1; x>=0; x--) {
bool loop = false;
for (int t : G[x]) if (x == t) loop = true;
bool next = false;
for (int t : G[x]) if (x != t) next = true;
//A
if (owner[x] == 1) {
if (color[x] && loop) win[x] = 1;
else {
if (next) win[x] = win[x+1];
else win[x] = 0;
}
}
else {
if (!color[x] && loop) win[x] = 0;
else {
if (next) win[x] = win[x+1];
else win[x] = 1;
}
}
}
return win;
}
else if (allA||allB) {
rep(i, M) if (U[i]==V[i]) self[i] = true;
vector<int> vs;
rep(i, N) used[i] = false;
rep(i, N) if (!used[i]) dfs(i, vs);
rep(i, N) used[i] = false;
int K = 0;
for (int i=vs.size()-1; i>=0; i--) if (!used[vs[i]]) {
dfs2(vs[i], K++);
}
rep(i, N) W[ord[i]].pb(i);
rep(i, N) if (!W[i].empty()) {
if (W[i].size() == 1 && !self[W[i][0]]) continue;
bool has = false;
for (int x : W[i]) if (color[x]) has = true;
if (allA) earn[i] |= has;
else earn[i] |= !has;
//if (earn[i]) cout<<"g="<<i<<" ({";for(int x:W[i])cout<<x<<",";cout<<"}): ok\n";
}
//cout<<"K="<<K<<"\n";
rep(i, M) {
if (ord[U[i]] != ord[V[i]]) {
//cout<<ord[U[i]]<<"->"<<ord[V[i]]<<"\n";
G2[ord[U[i]]].pb(ord[V[i]]);
}
}
rep(i, K) memo[i] = -1;
vector<int> ret(N, 0);
if (allB) rep(i, N) ret[i] = 1;
rep(i, K) if (dfs3(i)) {
//cout<<"g="<<i<<": yes\n";
for (int x : W[i]) {
if (allA) ret[x] = 1;
else ret[x] = 0;
}
}
return ret;
}
else abort();
}
