#include "train.h"
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
using vi = vector<int>;
#define sz(x) int(x.size())
//a = owner, r = charging
vi who_wins(vi a, vi r, vi U, vi V)
{
int n = sz(a);
int m = sz(U);
vi edge[n];
vi revedge[n];
for(int j = 0; j < m; j++)
{
edge[U[j]].push_back(V[j]);
revedge[V[j]].push_back(U[j]);
}
vi good(n, 0);
vi pushed(n, 0);
queue<int> tbv;
for(int i = 0; i < n; i++)
{
if(r[i])
{
good[i] = 1;
tbv.push(i);
pushed[i] = 1;
}
}
vi deg(n, 0);
for(int j = 0; j < m; j++)
deg[U[j]]++;
// cerr << "done\n";
while(!tbv.empty())
{
int u = tbv.front();
tbv.pop();
// cerr << "u = " << u << '\n';
for(int v : revedge[u])
{
if(pushed[v]) continue;
if(a[v] == 1)
{
pushed[v] = 1;
tbv.push(v);
good[v] = 1;
}
else
{
deg[v]--;
if(deg[v] == 0)
{
pushed[v] = 1;
tbv.push(v);
good[v] = 1;
}
}
}
}
while(1)
{
queue<int> tbv;
int oldsize = 0;
pushed = vi(n, 0);
for(int i = 0; i < n; i++)
{
oldsize += !good[i];
if(!good[i])
{
pushed[i] = 1;
tbv.push(i);
}
}
deg = vi(n, 0);
for(int j = 0; j < m; j++)
deg[U[j]]++;
while(!tbv.empty())
{
int u = tbv.front();
tbv.pop();
// cerr << "u = " << u << '\n';
for(int v : revedge[u])
{
if(pushed[v]) continue;
if(a[v] == 0)
{
pushed[v] = 1;
tbv.push(v);
good[v] = 0;
}
else
{
deg[v]--;
if(deg[v] == 0)
{
pushed[v] = 1;
tbv.push(v);
good[v] = 0;
}
}
}
}
int newsize = 0;
for(int i = 0; i < n; i++)
newsize += !good[i];
if(newsize == oldsize) break;
}
return good;
}
