#include <vector>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef vector<int> vi;
const int N = 300000, M = 300000, C = 30, INF = 0x3f3f3f3f;
int ii[M], jj[M], nxt[M * 2], head[N][C], tail[N][C]; char available[N][C];
void append(int i, int c, int h) {
if (head[i][c] == -1)
head[i][c] = h;
nxt[tail[i][c]] = h, tail[i][c] = h;
}
int pop(int i, int c) {
int h = head[i][c];
if ((head[i][c] = nxt[h]) == -1)
tail[i][c] = -1;
return h >> 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];
int find_(int i) {
return ds_[i] < 0 ? i : (ds_[i] = find_(ds_[i]));
}
void merge(int i, int j) {
int c;
for (c = 0; c < C; c++) {
available[i][c] |= available[j][c];
if (head[i][c] == -1)
head[i][c] = head[j][c], tail[i][c] = tail[j][c];
else if (head[j][c] != -1)
nxt[tail[i][c]] = head[j][c], tail[i][c] = tail[j][c];
}
}
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, merge(i, j);
}
int pp[N], qu[N], cnt;
void get(int i) {
int c;
pp[i] = -1;
for (c = 0; c < C; c++)
if (available[i][c])
while (head[i][c] != -1) {
int h = pop(i, c), j = i ^ find_(ii[h]) ^ find_(jj[h]);
if (j != i) {
pp[i] = j;
if (!join(i, j))
qu[cnt++] = i;
return;
}
}
}
vi find_reachable(vi aa, vi ii_, vi jj_, vi cc) {
int n = aa.size(), m = ii_.size(), h, i, j, c, mn, k;
vi ans(n);
for (h = 0; h < m; h++)
ii[h] = ii_[h], jj[h] = jj_[h];
for (i = 0; i < n; i++)
available[i][aa[i]] = 1;
for (i = 0; i < n; i++)
for (c = 0; c < C; c++)
head[i][c] = tail[i][c] = -1;
for (h = 0; h < m * 2; h++)
nxt[h] = -1;
for (h = 0; h < m; h++)
append(ii[h], cc[h], h << 1 | 0), append(jj[h], 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];
k = 0;
for (j = pp[i]; j != i; j = pp[j]) {
join_(i, j);
if (k++ >= N * 2)
return ans;
}
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;
}
