#include "bulb.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300100;
int N;
int L[MAXN], R[MAXN];
vector <int> vs;
vector <int> hs;
int llim;
bool bbad[MAXN], hbad[MAXN];
bool bfull;
int nc[MAXN];
void flood (int cloc, int cdep)
{
nc[cloc] = vs.size();
if (cloc < 0)
{
if (cloc == -2)
{
if (vs.size() > 2)
return;
if (vs.size() == 0)
{
// gg
llim = -100;
}
else if (vs.size() == 1)
{
// can't intercept after, or at unless this is the full path
if (cdep == N)
{
// must go at or before here
llim = min (llim, vs[0]);
}
else
{
// must go before here
llim = min (llim, vs[0] - 1);
}
}
else
{
int lo = hs[0], hi = hs[1];
hbad[lo] = hbad[hi] = true;
}
}
return;
}
flood (L[cloc], cdep + 1);
vs.push_back(cdep);
hs.push_back(cloc);
flood (R[cloc], cdep + 1);
vs.pop_back();
hs.pop_back();
}
int FindWinner(int T, std::vector<int> vl, std::vector<int> vr){
N = vl.size();
for (int i = 0; i < N; i++)
{
L[i] = vl[i];
R[i] = vr[i];
}
for (int i = 0; i < MAXN; i++)
{
bbad[i] = hbad[i] = false;
nc[i] = 0;
}
for (int i = 0; i < N; i++)
{
L[i] = vl[i];
R[i] = vr[i];
}
llim = 1e9;
flood (0, 0);
int cloc = 0, cdep = 0;
while (cloc >= 0)
{
if (!hbad[cloc] && cdep <= llim)
return 1;
cloc = L[cloc];
cdep++;
}
if (llim < 1e6)
return 0;
for (int i = 0; i < N; i++)
if (nc[i] >= 2 && !hbad[i])
return 1;
return 0;
}
