#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 3e5 + 5;
int n, m, par[NMAX], dfsn[NMAX], fin[NMAX], sz[NMAX], bad[NMAX], t, from[NMAX];
vector<int> E[NMAX];
set<int> K[NMAX];
map<int, vector<int>> mp[NMAX];
int find(int x){return par[x] == -1 ? x : par[x] = find(par[x]);}
void Union(int a, int b){
if(K[a].size() + mp[a].size() < K[b].size() + mp[b].size()) swap(K[a], K[b]), swap(mp[a], mp[b]);
for(auto&[k, v] : mp[b]){
if(K[a].find(k) == K[a].end()) {
if(mp[a][k].size() < v.size()) swap(mp[a][k], v);
for(auto&y : v) mp[a][k].emplace_back(y);
}
else{
if(E[a].size() < v.size()) swap(E[a], v);
for(auto& y : v) E[a].emplace_back(y);
}
}
for(auto& k : K[b]) K[a].emplace(k);
if(E[a].size() < E[b].size()) swap(E[a], E[b]);
for(auto& e : E[b]) E[a].emplace_back(e);
E[b].clear();
sz[a] += sz[b];
par[b] = a;
bad[a] |= bad[b];
return;
}
void dfs(int x){
dfsn[x] = ++t;
while(E[x].size()){
x = find(x);
int nx = find(E[x].back()); E[x].pop_back();
if(x == nx) continue;
if(!dfsn[nx]){
from[nx] = x;
dfs(nx);
}
else if(!fin[nx]){
for(int i = x; i != nx; i = from[i]) Union(nx, i);
}
if(find(nx) != find(x)) bad[x] = 1;
}
fin[x] = 1;
return;
}
vector<int> find_reachable(vector<int>r, vector<int> u, vector<int> v, vector<int> c){
n = r.size(); m = u.size();
auto add_edge = [&](int& a, int& b, int& c){
if(r[a] == c) E[a].emplace_back(b);
else mp[a][c].emplace_back(b);
};
for(int i = 0; i < m; i++){
add_edge(u[i], v[i], c[i]);
add_edge(v[i], u[i], c[i]);
}
memset(par, -1, sizeof(par));
for(int i = 0; i < n; i++) sz[i] = 1, K[i].emplace(r[i]);
for(int i = 0; i < n; i++)
if(!dfsn[i]) dfs(i);
vector<int> res(n, 0);
int mn = n + 1;
for(int i = 0; i < n; i++) if(!bad[find(i)]) mn = min(mn, sz[find(i)]);
for(int i = 0; i < n; i++) if(!bad[find(i)] && sz[find(i)] == mn) res[i] = 1;
return res;
}
/*
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> r(n), u(m), v(m), c(m);
for(auto& i : r) cin >> i;
for(auto& i : u) cin >> i;
for(auto& i : v) cin >> i;
for(auto& i : c) cin >> i;
vector<int> res = find_reachable(r, u, v, c);
for(int i = 0; i < n; i++) cout << res[i] << ' ';
return 0;
}
*/
/*
test1
4 5
0 1 1 2
0 0 1 1 3
1 2 2 3 1
0 0 1 0 2
test2
7 10
0 1 1 2 2 1 2
0 0 1 1 2 3 3 4 4 5
1 2 2 3 3 4 5 5 6 6
0 0 1 0 0 1 2 0 2 1
test3
3 1
0 0 0
0 1 0
*/
