#include <vector>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef vector<int> vi;
const int N = 300000, M = 300000, L = 19, N_ = 1 + (N + M * 2) * (L + 1), INF = 0x3f3f3f3f; /* L = ceil(log2(N)) */
int ii[M], jj[M], nxt[M * 2];
int ll[N_], rr[N_], head[N_], tail[N_], _; char available[N_], has[N_];
int n;
void pul_leaf(int t) {
has[t] = available[t] && head[t] != -1;
}
void pul(int t) {
has[t] = has[ll[t]] || has[rr[t]];
}
void push(int t, int h) {
if (head[t] == -1)
head[t] = tail[t] = h;
else
nxt[tail[t]] = h, tail[t] = h;
}
int pop(int t) {
int h = head[t];
if ((head[t] = nxt[h]) == -1)
tail[t] = -1;
return h >> 1;
}
int update(int t, int l, int r, int c, int h) {
if (t == 0)
t = ++_, head[t] = tail[t] = -1;
if (r - l == 1) {
if (h != -1)
push(t, h);
else
available[t] = 1;
pul_leaf(t);
} else {
int m = (l + r) / 2;
if (c < m)
ll[t] = update(ll[t], l, m, c, h);
else
rr[t] = update(rr[t], m, r, c, h);
pul(t);
}
return t;
}
int merge(int t1, int t2, int l, int r) {
int m;
if (t1 == 0)
return t2;
if (t2 == 0)
return t1;
if (r - l == 1) {
available[t1] |= available[t2];
if (head[t1] == -1)
head[t1] = head[t2], tail[t1] = tail[t2];
else
nxt[tail[t1]] = head[t2], tail[t1] = tail[t2];
pul_leaf(t1);
} else {
m = (l + r) / 2;
ll[t1] = merge(ll[t1], ll[t2], l, m), rr[t1] = merge(rr[t1], rr[t2], m, r);
pul(t1);
}
return t1;
}
int find_(int i);
int query(int t, int l, int r, int i) {
if (!has[t])
return -1;
if (r - l == 1) {
while (head[t] != -1) {
int h = pop(t), j = i ^ find_(ii[h]) ^ find_(jj[h]);
if (j != i) {
pul_leaf(t);
return j;
}
}
pul_leaf(t);
return -1;
} else {
int m = (l + r) / 2, j;
if ((j = query(ll[t], l, m, i)) != -1) {
pul(t);
return j;
}
if ((j = query(rr[t], m, r, i)) != -1) {
pul(t);
return j;
}
pul(t);
return -1;
}
}
int ds[N];
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
int join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return 0;
if (ds[i] > ds[j])
ds[i] = j;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i;
}
return 1;
}
int ds_[N], tt[N];
int find_(int i) {
return ds_[i] < 0 ? i : (ds_[i] = find_(ds_[i]));
}
void join_(int i, int j) {
int tmp;
i = find_(i);
j = find_(j);
if (i == j)
return;
if (ds_[i] > ds_[j])
tmp = i, i = j, j = tmp;
ds_[i] += ds_[j], ds_[j] = i, tt[i] = merge(tt[i], tt[j], 0, n);
}
int pp[N], qu[N], cnt;
void get(int i) {
int j = query(tt[i], 0, n, i);
if (j != -1) {
pp[i] = j;
if (!join(i, j))
qu[cnt++] = i;
} else
pp[i] = -1;
}
vi find_reachable(vi aa, vi ii_, vi jj_, vi cc) {
int m = ii_.size(), h, i, j, mn;
vi ans(n = aa.size());
for (h = 0; h < m; h++)
ii[h] = ii_[h], jj[h] = jj_[h];
for (i = 0; i < n; i++)
tt[i] = update(tt[i], 0, n, aa[i], -1);
for (h = 0; h < m * 2; h++)
nxt[h] = -1;
for (h = 0; h < m; h++) {
i = ii[h], j = jj[h];
tt[i] = update(tt[i], 0, n, cc[h], h << 1 | 0), tt[j] = update(tt[j], 0, n, cc[h], h << 1 | 1);
}
memset(ds, -1, n * sizeof *ds), memset(ds_, -1, n * sizeof *ds_);
for (i = 0; i < n; i++)
get(i);
while (cnt--) {
i = qu[cnt];
for (j = find_(pp[i]); j != find_(i); j = find_(pp[j]))
join_(i, j);
get(find_(i));
}
mn = INF;
for (i = 0; i < n; i++)
if (ds_[i] < 0 && pp[i] == -1)
mn = min(mn, -ds_[i]);
for (i = 0; i < n; i++)
ans[i] = pp[find_(i)] == -1 && -ds_[find_(i)] == mn;
return ans;
}
