#include "train.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
void first_dfs(ll n, vector<bool> &vis, vector<vector<ll>> &g, vector<ll> &ord){
ord.push_back(n);
vis[n] = 1;
for(ll i: g[n]) if(!vis[i]) first_dfs(i, vis, g, ord);
}
void second_dfs (ll n, vector<bool> &vis, vector<vector<ll>> &g, vector<ll> &c, ll col){
vis[n] = 1; c[n] = col;
for(ll i: g[n]) if(!vis[i]) second_dfs(i, vis, g, c, col);
}
vector<vector<ll>> build_DAG(ll n, ll cnt, vector<vector<ll>> &g, vector<ll> &col){
vector<vector<ll>> dag(cnt);
for(ll i = 0; i < n; i++) {
for(ll j: g[i]) if(col[j] != col[i]) dag[col[j]].push_back(col[i]), dag[col[i]].push_back(col[j]);
}
return dag;
}
vector<ll> top_sort(ll n, vector<vector<ll>> &g){
vector<ll> deg(n);
for(ll i = 0; i < n; i++) deg[i] = g[i].size();
queue<ll> q;
for(ll i= 0; i < n; i++) if(deg[i] == 1) q.push(i);
vector<ll> ts;
while(q.size()){
ll node = q.front(); q.pop();
ts.push_back(node);
for(ll i : g[node]){
deg[i]--;
if(deg[i] == 0) q.push(i);
}
}
return ts;
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
ll n = a.size(), m = u.size();
vector<bool> self_loop(n);
vector<vector<ll>> g(n), rg(n);
for(ll i = 0; i < m; i++){
if(u[i] == v[i]) self_loop[u[i]] = 1;
g[u[i]].push_back(v[i]), g[v[i]].push_back(u[i]);
}
vector<bool> vis_g(n), vis_rg(n);
vector<ll> ord;
for(ll i = 0; i < n; i++) if(!vis_g[i]) first_dfs(i, vis_g, g, ord);
ll cnt = 0;
vector<ll> col(n);
for(ll i: ord) if(!vis_rg[i]) second_dfs(i, vis_rg, rg, col, ++cnt);
cnt++;
vector<vector<ll>> comp(cnt);
for(ll i = 0; i < n; i++) comp[col[i]].push_back(i);
vector<vector<ll>> dag = build_DAG(n, cnt, g, col);
vector<ll> ts = top_sort(cnt, g);
reverse(ts.begin(), ts.end());
vector<ll> dp(cnt);
for(ll i: ts){
if(comp[i].size() == 1) {
dp[i] = self_loop[i] && r[i];
}
else{
for(ll j: comp[i]) if(r[i]) dp[i] = 1;
}
for(ll j: dag[i]) dp[i] = max(dp[i], dp[j]);
}
vector<ll> ans(n);
for(ll i = 0; i < n; i++) ans[i] = dp[col[i]];
return ans;
}
