#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef vector<int> vi;
#define N 300000
int que[N], que_[N], head, tail, *ej[N], *ec[N], eo[N];
int ds[N], gg[N], *ej_[N], eo_[N], ff[N], col[N];
int n, id, tt[N], *wi[N], wo[N], vis[N], td;
void append_(int i, int j) {
int o = eo_[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej_[i] = (int *) realloc(ej_[i], o * 2 * sizeof ej_[i]);
ej_[i][o] = j;
}
void append(int i, int j, int c) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof ej[i]),
ec[i] = (int *) realloc(ec[i], o * 2 * sizeof ec[i]);
ej[i][o] = j, ec[i][o] = c;
}
int find(int i) {
return ds[i] == i ? i : (ds[i] = find(ds[i]));
}
void join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return;
ds[i] = j;
}
void upd(int i) {
ff[i] = 1, que_[td++] = i;
while (wo[i] > 0) {
int i_ = wi[i][--wo[i]];
if (!vis[i_])
vis[i_] = 1, que[tail++] = i_;
}
}
int st;
void add(int i) {
int o;
upd(col[i]);
vis[i] = 1;
if (find(i) != find(st))
return;
for (o = eo[i]; o--; ) {
int j = ej[i][o], c = ec[i][o];
if (vis[j])
continue;
if (ff[c] == 1)
que[tail++] = j, vis[j] = 1;
else
que_[td++] = c, wi[c][wo[c]++] = j;
}
}
void bfs(int i) {
int i_, o;
st = i, head = tail = td = 0;
que[tail++] = i;
while (head < tail) {
i_ = que[head++];
if (find(i_) != find(i)) {
id = i_;
break;
}
add(i_);
}
for (i_ = 0; i_ < tail; i_++)
vis[que[i_]] = 0;
for (i_ = 0; i_ < td; i_++)
ff[que_[i_]] = 0, wo[que_[i_]] = 0;
}
vi find_reachable(vi aa, vi ii_, vi jj_, vi cc) {
static int ii[N], jj[N], hh[N];
int m = ii_.size(), i, j, i_, mn, op, cnt;
vi ans(n = aa.size());
for (i = 0; i < n; i++)
ej_[i] = (int *) malloc(2 * sizeof *ej_[i]),
ej[i] = (int *) malloc(2 * sizeof *ej[i]),
ec[i] = (int *) malloc(2 * sizeof *ec[i]);
for (i = 0; i < m; i++)
append(ii_[i], jj_[i], cc[i]), append(jj_[i], ii_[i], cc[i]);
for (i = 0; i < n; i++)
ds[i] = i, gg[i] = 0;
for (i = 0; i < n; i++)
col[i] = aa[i], tt[aa[i]]++;
for (i = 0; i < m; i++)
tt[cc[i]]++;
for (i = 0; i < N; i++)
if (tt[i] >= 1)
wi[i] = (int *) malloc(2 * tt[i] * sizeof *wi[i]), wo[i] = 0;
cnt = 0;
for (i_ = 0; i_ < 20; i_++) {
op = 0;
for (i = 0; i < n; i++)
if (find(i) == i && gg[i] == 0) {
id = -1;
bfs(i);
if (id == -1) {
gg[i] = 1, hh[cnt++] = i;
for (j = 0; j < tail; j++)
append_(i, que[j]);
} else
ii[op] = i, jj[op++] = id;
}
for (i = 0; i < op; i++)
join(ii[i], jj[i]);
}
for (i = 0, mn = n + 1; i < cnt; i++)
mn = min(mn, eo_[hh[i]]);
for (i = 0; i < cnt; i++)
if (eo_[hh[i]] == mn)
for (j = 0; j < eo_[hh[i]]; j++)
ans[ej_[hh[i]][j]] = 1;
return ans;
}
