#include <vector>
#include <algorithm>
#include <tuple>
#include <set>
#include <map>
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ff first
#define ss second
using namespace std;
//namespace A{
const int INF = (int)1e9 + 7;
vector<int> R, C;
vector<pii> gph[303030];
map<int, int> edge[303030];
map<int, vector<int>> ver[303030];
set<int> key[303030];
vector<pii> ran;
int ord[303030];
int rev[303030];
int cnt = 0;
int val = 0;
int dfs(int x)
{
int ret = ord[x] = ++cnt;
rev[cnt] = x;
vector<int> Q;
for(auto [y, c] : gph[x])
{
if(c == R[x]) Q.push_back(y);
else if(!ord[y]) ver[x][c].push_back(y);
else
{
if(edge[x].count(c)) edge[x][c] = min(edge[x][c], ord[y]);
else edge[x][c] = ord[y];
}
}
key[x].insert(R[x]);
while(Q.size())
{
int y = Q.back(); Q.pop_back();
if(!ord[y])
{
int t = dfs(y);
if(t == -1) return -1;
ret = min(ret, t);
if(ver[x].size() + edge[x].size() + key[x].size() < ver[y].size() + edge[y].size() + key[x].size())
{
swap(ver[x], ver[y]);
swap(edge[x], edge[y]);
swap(key[x], key[y]);
}
for(int c : key[y])
{
if(ver[x].count(c))
{
for(int z : ver[x][c]) Q.push_back(z);
ver[x].erase(c);
}
if(edge[x].count(c))
{
ret = min(ret, edge[x][c]);
ver[x].erase(c);
}
key[x].insert(c);
}
for(auto [c, val] : edge[y])
{
if(key[x].count(c)) ret = min(ret, val);
else
{
if(edge[x].count(c)) edge[x][c] = min(edge[x][c], val);
else edge[x][c] = val;
}
}
for(auto &[c, v] : ver[y])
{
if(key[x].count(c)) for(auto z : v) Q.push_back(z);
else
{
if(ver[x].count(c))
{
if(ver[x][c].size() < v.size()) swap(ver[x][c], v);
for(auto z : v) ver[x][c].push_back(z);
}
else ver[x][c] = v;
}
}
}
else ret = min(ret, ord[y]);
}
if(ret < val) { val = ord[x] + 1; return -1; }
if(ret >= ord[x])
{
ran.push_back({ord[x], cnt});
val = cnt + 1;
return -1;
}
return ret;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
int n = r.size();
int m = u.size();
// init();
R = r, C = c;
for(int i = 0; i < m; ++i)
{
gph[u[i]].push_back({v[i], c[i]});
gph[v[i]].push_back({u[i], c[i]});
}
for(int i = 0; i < n; ++i) if(!ord[i]) dfs(i);
int mn = INF;
for(auto [x, y] : ran) mn = min(mn, y - x);
vector<int> ans(n);
for(auto [x, y] : ran) if(mn == y - x)
{
for(int i = x; i <= y; ++i)
ans[rev[i]] = 1;
}
return ans;
}
//}
//
//namespace B{
//
// vector<pii> gph[303030];
//
// void init(int n)
// {
// for(int i = 0; i < n; ++i) gph[i].clear();
// }
//
// vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
// {
// int n = r.size();
// int m = u.size();
// init(n);
// for(int i = 0; i < m; ++i)
// {
// gph[u[i]].push_back({v[i], c[i]});
// gph[v[i]].push_back({u[i], c[i]});
// }
//
// int cnt[n]{};
// int mn = n;
// for(int x = 0; x < n; ++x)
// {
// bool vst[n]{};
// bool col[n]{};
// vector<int> Q;
// vector<int> ls[n];
// Q.push_back(x);
// while(Q.size())
// {
// int i = Q.back(); Q.pop_back();
// if(vst[i]) continue;
// vst[i] = true;
// if(!col[r[i]])
// {
// for(auto j : ls[r[i]]) Q.push_back(j);
// col[r[i]] = true;
// }
// for(auto [j, e] : gph[i])
// {
// if(col[e]) Q.push_back(j);
// else ls[e].push_back(j);
// }
// }
// for(int i = 0; i < n; ++i) if(vst[i]) ++cnt[x];
// mn = min(mn, cnt[x]);
// }
//
// vector<int> ans(n);
// for(int i = 0; i < n; ++i) if(cnt[i] == mn) ans[i] = 1;
// return ans;
// }
//}
