#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 300'007;
int tab[N], vis[N];
bool czy[N];
int fau[N], siz[N];
set<pair<int, int>> imp[N];
set<int> pos[N], key[N];
vector<pair<int, int>> ed[N];
stack<int> sta;
int Find(int v)
{
if(fau[v] == v) return v;
return (fau[v] = Find(fau[v]));
}
void Union(int a, int b)
{
a = Find(a); b = Find(b);
if(a == b) return;
if((int)(pos[a].size() + imp[a].size() + key[a].size()) < (int)(pos[b].size() + imp[b].size() + key[b].size()))
swap(a, b);
fau[b] = a;
for(set<int>::iterator it = key[b].begin(); it != key[b].end(); ++it)
{
int x = *it;
set<pair<int, int>>::iterator it2 = imp[a].lower_bound(make_pair(x, 0));
while(it2 != imp[a].end() && (*it2).st == x)
{
pos[a].insert((*it2).nd);
imp[a].erase(it2);
it2 = imp[a].lower_bound(make_pair(x, 0));
}
key[a].insert(x);
}
key[b].clear();
for(set<int>::iterator it = pos[b].begin(); it != pos[b].end(); ++it)
pos[a].insert(*it);
pos[b].clear();
for(set<pair<int, int>>::iterator it = imp[b].begin(); it != imp[b].end(); ++it)
{
if(key[a].find((*it).st) != key[a].end())
pos[a].insert((*it).nd);
else
imp[a].insert(*it);
}
imp[b].clear();
}
void DFS()
{
while(sta.size() > 0)
{
int v = sta.top();
vis[v] = 1;
if((int)pos[v].size() == 0)
{
vis[v] = 2;
sta.pop();
continue;
}
int ne = *(pos[v].begin()); pos[v].erase(pos[v].begin());
ne = Find(ne);
if(vis[ne] == 2 || ne == v) continue;
if(vis[ne] == 0)
{
sta.push(ne);
continue;
}
sta.pop();
while(sta.top() != ne)
{
Union(v, sta.top());
sta.pop();
}
Union(v, ne);
sta.pop();
sta.push(Find(v));
}
}
vector<int> find_reachable(vector<int> _r, vector<int> _u, vector<int> _v, vector<int> _c)
{
int n = _r.size(), m = _u.size();
for(int i = 0; i < m; ++i)
{
ed[_u[i] + 1].pb(make_pair(_v[i] + 1, _c[i]));
ed[_v[i] + 1].pb(make_pair(_u[i] + 1, _c[i]));
}
for(int i = 1; i <= n; ++i)
{
fau[i] = i; czy[i] = true;
tab[i] = _r[i - 1];
key[i].insert(tab[i]);
for(int j = 0; j < (int)ed[i].size(); ++j)
if(ed[i][j].nd == tab[i])
pos[i].insert(ed[i][j].st);
else
imp[i].insert(make_pair(ed[i][j].nd, ed[i][j].st));
}
for(int i = 1; i <= n; ++i)
{
if(vis[i] == 0)
{
sta.push(i);
DFS();
}
}
int mi = n * 10;
for(int i = 1; i <= n; ++i)
{
int v = Find(i);
if(czy[v] == false) continue;
++siz[v];
for(int j = 0; j < (int)ed[i].size(); ++j)
{
int ne = Find(ed[i][j].st);
if(ne != v && key[v].find(ed[i][j].nd) != key[v].end())
czy[v] = false;
}
}
for(int i = 1; i <= n; ++i)
if(Find(i) == i && czy[i])
mi = min(mi, siz[i]);
vector<int> answer;
for(int i = 1; i <= n; ++i)
if(czy[Find(i)] && siz[Find(i)] == mi)
answer.pb(1);
else
answer.pb(0);
return answer;
}
