#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 5000;
const int MAXM = 20000;
int N, M, A[MAXN+10], R[MAXN+10], ans[MAXN+10];
vector<int> adj[MAXN+10], radj[MAXN+10];
int nxt[MAXN+10];
bool vis[MAXN+10];
void dfs(int now)
{
vis[now]=1;
for(int nxt : adj[now])
{
if(vis[nxt]) continue;
if(R[nxt]) continue;
dfs(nxt);
}
}
void rdfs(int now)
{
vis[now]=1;
for(int nxt : radj[now])
{
if(vis[nxt]) continue;
rdfs(nxt);
}
}
vector<int> who_wins(vector<int> _A, vector<int> _R, vector<int> _U, vector<int> _V)
{
N=_A.size(); M=_U.size();
for(int i=1; i<=N; i++)
{
A[i]=_A[i-1];
R[i]=_R[i-1];
}
for(int i=0; i<M; i++)
{
int u=_U[i]+1, v=_V[i]+1;
adj[u].push_back(v);
radj[v].push_back(u);
}
for(int i=1; i<=N; i++)
{
if(adj[i].size()==1)
{
nxt[i]=adj[i][0];
continue;
}
if(A[i])
{
if(R[i]) nxt[i]=i;
else nxt[i]=i+1;
}
else
{
if(R[i]) nxt[i]=i+1;
else nxt[i]=i;
}
}
for(int i=N; i>=1; i--)
{
if(nxt[i]==i) ans[i]=R[i];
else ans[i]=ans[i+1];
}
vector<int> _ans(N);
for(int i=1; i<=N; i++) _ans[i-1]=ans[i];
return _ans;
}
