#include <cassert>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
const int MN = 3e5+10;
int N, M;
struct edge
{
public:
int n, w;
bool operator < (const edge& o) const {return w < o.w || !(o.w < w) && n < o.n;}
};
struct DSU
{
public:
std::vector<int> p, r;
DSU(int N): p(N, -1), r(N, 0) {}
int find(int n) {return p[n]==-1 ? n : p[n]=find(p[n]);}
bool merge(int a, int b)
{
a=find(a), b=find(b);
assert(a!=b);
if(a==b) return 0;
if(r[a]<r[b]) std::swap(a,b);
p[b]=a, r[a]+=r[a]==r[b], r[b]=-1;
return 1;
}
};
DSU dsu(MN);
std::set<edge> a[MN];
std::set<int> col[MN];
std::vector<int> todo[MN];
int d[MN], l[MN], ctr, cc, sz[MN]; // scc
bool in_stack[MN], out[MN], good[MN];
std::stack<int> stk;
std::vector<int> g[MN];
void dfs(int n)
{
d[n] = l[n] = ctr++;
stk.push(n);
in_stack[n] = 1;
for(;!todo[n].empty();)
{
int x=todo[n].back(); todo[n].pop_back();
if(d[x] == -1)
{
dfs(x), ckmin(l[n], l[x]);
if(!in_stack[x])
out[n]=1;
}
else if(in_stack[x])
ckmin(l[n], d[x]);
else
out[n]=1;
int u=dsu.find(n), v=dsu.find(x);
if(u!=v)
{
dsu.merge(u, v);
if(dsu.p[v] == -1) std::swap(u,v);
//v -> u
if(col[u].size()+a[u].size() < col[v].size()+a[v].size())
col[u].swap(col[v]), a[u].swap(a[v]);
for(int c:col[v])
if(col[u].insert(c).second)
{
auto it=a[u].lower_bound({-1,c});
for(;it != a[u].end() && it->w == c;it=a[u].erase(it))
todo[n].push_back(it->n);
}
for(auto c:a[v])
if(col[u].find(c.w) != col[u].end())
todo[n].push_back(c.n);
else a[u].insert(c);
col[v].clear();
a[v].clear();
}
/*
printf("MERGE %d - %d\n", n, x);
printf("COL: "); for(auto z:col[dsu.find(n)]) printf("%d ", z); printf("\n");
printf("EDG: "); for(auto z:a[dsu.find(n)]) printf("(%d,%d) ", z.n, z.w); printf("\n");
*/
}
if(l[n] == d[n])
{
++cc;
good[cc]=1;
for(;;)
{
int x=stk.top(); stk.pop();
++sz[cc];
if(out[x]) good[cc]=0;
g[cc].push_back(x);
in_stack[x] = 0;
if(x == n) break;
}
}
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c)
{
memset(d, -1, sizeof d);
N = r.size();
M = u.size();
std::vector<int> ans(r.size(), 0);
for(int i=0;i<M;++i)
{
a[u[i]].insert({v[i], c[i]});
a[v[i]].insert({u[i], c[i]});
}
for(int i=0;i<N;++i)
{
col[i].insert(r[i]);
auto it=a[i].lower_bound({-1,r[i]});
for(;it != a[i].end() && it->w == r[i];it = a[i].erase(it))
todo[i].push_back(it->n);
}
for(int i=0;i<N;++i)
{
if(d[i] == -1)
dfs(i);
}
int msz=N;
for(int i=1;i<=cc;++i)
if(good[i])
ckmin(msz, sz[i]);
for(int i=1;i<=cc;++i)
if(good[i] && sz[i] == msz)
for(int x:g[i])
ans[x]=1;
return ans;
}
