#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
const int MXN = 3e5 + 5;
struct DSU
{
vector<int> e, lab;
void init(int n)
{
e.assign(n, -1);
lab.resize(n);
iota(lab.begin(), lab.end(), 0);
}
int get(int x)
{
if (e[x] < 0) return x;
return e[x] = get(e[x]);
}
int getlab(int x)
{
return lab[get(x)];
}
void unite(int x, int y)
{
// y -> x
x = get(x), y = get(y);
if (x == y) return;
if (e[x] < e[y])
{
e[x] += e[y];
e[y] = x;
}
else
{
lab[y] = lab[x];
e[y] += e[x];
e[x] = y;
}
}
};
int n;
vector<array<int, 2>> adj[MXN];
vector<int> r, c;
queue<int> q;
map<int, vector<int>> mp;
set<int> keys;
DSU dsu;
int found[MXN];
int ans[MXN];
int used[MXN];
vector<int> find_reachable(vector<int> R, vector<int> u, vector<int> v, vector<int> C)
{
n = R.size(), r = R, c = C;
dsu.init(n);
for (int i = 0; i < u.size(); i++)
{
adj[u[i]].push_back({v[i], c[i]});
adj[v[i]].push_back({u[i], c[i]});
}
fill(found, found + MXN, 1);
while (1)
{
vector<array<int, 2>> vv;
vector<int> alive, cc;
for (int i = 0; i < n; i++)
{
if (dsu.getlab(i) == i && found[i]) alive.push_back(i);
}
for (int &i : alive)
{
// cout << "! " << i << ' ';
while (!q.empty()) q.pop();
mp.clear(), keys.clear();
found[i] = 0;
used[i] = 1;
cc = {i};
q.push(i);
// cout << i << ": ";
while (!q.empty())
{
int x = q.front();
q.pop();
// cout << x << ' ';
if (dsu.getlab(x) != i)
{
found[i] = 1;
vv.push_back({dsu.get(i), dsu.get(x)});
break;
}
if (mp.find(r[x]) != mp.end())
{
vector<int> &v = mp[r[x]];
while (!v.empty())
{
if (!used[v.back()])
{
used[v.back()] = 1;
cc.push_back(v.back());
q.push(v.back());
}
v.pop_back();
}
}
keys.insert(r[x]);
for (array<int, 2> &v : adj[x])
{
// cout << v[0] << ' ' << v[1] << ", ";
if (used[v[0]]) continue;
if (keys.find(v[1]) == keys.end()) mp[v[1]].push_back(v[0]);
else
{
used[v[0]] = 1;
cc.push_back(v[0]);
q.push(v[0]);
}
}
// cout << " | ";
}
// cout << '\n';
for (int &i : cc) used[i] = 0;
cc.clear();
}
for (array<int, 2> &i : vv)
{
dsu.unite(i[1], i[0]);
// cout << i[0] << " -> " << i[1] << '\n';
}
if (vv.empty()) break;
}
int mn = n * 100;
for (int i = 0; i < n; i++)
{
if (dsu.getlab(i) != i) continue;
while (!q.empty()) q.pop();
vector<int> cc;
mp.clear(), keys.clear();
used[i] = 1;
cc = {i};
q.push(i);
while (!q.empty())
{
int x = q.front();
q.pop();
if (mp.find(r[x]) != mp.end())
{
vector<int> &v = mp[r[x]];
while (!v.empty())
{
if (!used[v.back()])
{
used[v.back()] = 1;
cc.push_back(v.back());
q.push(v.back());
}
v.pop_back();
}
}
for (array<int, 2> &v : adj[x])
{
if (used[v[0]]) continue;
if (keys.find(v[1]) == keys.end()) mp[v[1]].push_back(v[0]);
else
{
used[v[0]] = 1;
cc.push_back(v[0]);
q.push(v[0]);
}
}
}
for (int &j : cc)
{
ans[j] = cc.size();
}
mn = min(mn, ans[cc[0]]);
for (int &i : cc) used[i] = 0;
}
vector<int> res(n, 0);
for (int i = 0; i < n; i++)
{
if (ans[i] == mn) res[i] = 1;
}
return res;
}
