#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)a.size())
const int N = 5e2 + 5, M = N * (N - 1) / 2;
struct disjoint_set{
int par[N];
void reset(int n = N){
fill(par, par + n, -1);
}
disjoint_set(){
reset();
}
int root(int x){
return (par[x] < 0 ? x : (par[x] = root(par[x])));
}
bool merge(int x, int y){
if ((x = root(x)) == (y = root(y))){
return false;
}
if (par[x] > par[y]){
swap(x, y);
}
par[x] += par[y];
par[y] = x;
return true;
}
} dsu;
struct weighted_disjoint_set{
pair <int, int> par[M];
void reset(int n = M){
fill(par, par + n, pair{-1, 0});
}
weighted_disjoint_set(){
reset();
}
pair <int, int> root(int x){
if (par[x].fi < 0){
return pair{x, 0};
}
pair <int, int> ans = root(par[x].fi);
ans.se ^= par[x].se;
return (par[x] = ans);
}
bool share(int x, int y){
return (root(x).fi == root(y).fi);
}
int dist(int x, int y){
return (root(x).se ^ root(y).se);
}
bool merge(int x, int y, int val){
auto [tx, vx] = root(x);
auto [ty, vy] = root(y);
if (tx == ty){
return false;
}
val ^= vx ^ vy;
if (par[tx].fi > par[ty].fi){
swap(tx, ty);
}
par[tx].fi += par[ty].fi;
par[ty] = pair{tx, val};
return true;
}
} wdsu;
int n, m;
pair <int, int> edge[M];
int adj[N][N];
vector <int> vadj[N];
vector <int> find_spanning_tree(){
vector <int> ans;
For(i, 0, m){
auto [u, v] = edge[i];
if (dsu.merge(u, v)){
ans.emplace_back(i);
}
}
return ans;
}
namespace subtask123{
bool check(){
return n <= 240;
}
int msk[N];
vector <int> vadj_tree[N];
int known_edge[M];
void dfs_msk(int u, int p, int val){
msk[u] = val;
for (auto v: vadj_tree[u]){
if (v == p){
continue;
}
dfs_msk(v, u, val);
}
}
vector <int> solve(){
vector <int> mst = find_spanning_tree();
// cout << "mst" << endl;
// for (auto i: mst){
// cout << i << ' ';
// }
// cout << endl;
int count_mst = count_common_roads(mst);
for (auto i: mst){
auto &[u, v] = edge[i];
vadj_tree[u].emplace_back(v);
vadj_tree[v].emplace_back(u);
}
fill(known_edge, known_edge + m, -1);
for (auto id: mst){
vector <int> rem_mst;
for (auto i: mst){
if (i != id){
rem_mst.emplace_back(i);
}
}
auto query = [&](int i){
rem_mst.emplace_back(i);
int ans = count_common_roads(rem_mst);
rem_mst.pop_back();
return ans;
};
auto &[s, t] = edge[id];
dfs_msk(s, t, s);
dfs_msk(t, s, t);
// cout << "id " << id << endl;
// For(u, 0, n){
// cout << msk[u] << ' ';
// }
// cout << endl;
For(i, 0, m){
if (i == id){
continue;
}
auto &[u, v] = edge[i];
if (msk[u] == msk[v]){
continue;
}
if (wdsu.share(i, id)){
// cout << "share " << id << ' ' << i << ' ' << wdsu.dist(i, id) << endl;
if (known_edge[id] == -1 and wdsu.dist(i, id)){
int cur = query(i);
if (cur < count_mst){
known_edge[id] = 1;
}
else{
known_edge[id] = 0;
}
}
continue;
}
// cout << "new connection " << id << ' ' << i << endl;
int cur = query(i);
// cout << cur << ' ' << count_mst << endl;
if (cur < count_mst){
known_edge[id] = 1;
wdsu.merge(i, id, 1);
}
else if (cur > count_mst){
known_edge[id] = 0;
wdsu.merge(i, id, 1);
}
else{
wdsu.merge(i, id, 0);
}
}
if (known_edge[id] == -1){
known_edge[id] = 1;
}
// cout << "known_edge " << id << ' ' << known_edge[id] << endl;
}
For(i, 0, m){
if (known_edge[i] != -1){
auto [j, w] = wdsu.root(i);
known_edge[j] = known_edge[i] ^ w;
}
}
For(i, 0, m){
if (known_edge[i] == -1){
auto [j, w] = wdsu.root(i);
known_edge[i] = known_edge[j] ^ w;
}
}
vector <int> ans;
For(i, 0, m){
if (known_edge[i]){
ans.emplace_back(i);
}
}
return ans;
}
}
vector <int> find_roads(int _n, vector <int> _u, vector <int> _v){
n = _n;
m = isz(_u);
For(u, 0, n){
For(v, 0, n){
adj[u][v] = -1;
}
}
For(i, 0, m){
int u = _u[i], v = _v[i];
edge[i] = pair{u, v};
adj[u][v] = adj[v][u] = i;
vadj[u].emplace_back(i);
vadj[v].emplace_back(i);
}
if (subtask123::check()){
return subtask123::solve();
}
return {};
}
