// In the name of Allah
#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = (1 << 18) + 4;
const int limit = 8000;
int n, m, Qt;
vector<pii> adj[maxn];
vector<pii> E; int M[maxn];
int p[maxn], valx[maxn];
int mark[maxn], col[maxn], c;
vector<int> lsx[maxn], Ex, Rx, ans;
int valR[maxn]; vector<pii> resx;
int askx() {
if (Qt + 1 > limit) exit(23);
int x = count_common_roads(Ex); Qt++;
return x;
}
int get(int a) {
return (p[a] == a) ? a : p[a] = get(p[a]);
}
void merge(int a, int b) {
a = get(a); b = get(b);
if (a == b) return ;
if (valx[a] != -1) valx[b] = valx[a];
else if (valx[b] != -1) valx[a] = valx[b];
p[a] = b;
}
void dfs(int v) {
mark[v] = 1; col[v] = c;
for (auto f : adj[v]) {
int u = f.F, j = f.S;
if (!mark[u]) {
Ex.pb(j);
dfs(u);
}
}
}
void dfsx(int v, int p = -1) {
bool okx = 0;
for (auto f : adj[v]) {
int u = f.F, j = f.S;
if (!M[u]) {
okx = 1;
break;
}
}
if (!okx) return ;
fill(mark, mark + n, 0);
mark[v] = 1; c = 0; Ex.clear();
for (int i = 0; i < n; i++) {
if (!mark[i]) {
lsx[c].clear(); dfs(i); c++;
}
}
int vx = -1;
vector<int> vc;
for (auto f : adj[v]) {
int u = f.F, j = f.S;
if (!M[u]) {
lsx[col[u]].pb(j);
vc.pb(u); M[u] = 1;
Rx.pb(j);
}
else if (vx == -1 && u == p) {
lsx[col[u]].pb(j); vx = u;
}
}
for (int i = 0; i < c; i++) {
Ex.pb(lsx[i].back());
}
for (int i = 0; i < c; i++) {
Ex.erase(find(all(Ex), lsx[i].back()));
for (int j = 0; j < len(lsx[i]); j++) {
int x = lsx[i][j];
Ex.pb(x); valR[j] = askx(); Ex.pop_back();
}
for (int j = 1; j < len(lsx[i]); j++) {
int x1 = lsx[i][j - 1], x2 = lsx[i][j];
int R1 = valR[j - 1], R2 = valR[j];
if (R1 > R2) {
valx[get(x1)] = 1; valx[get(x2)] = 0;
}
else if (R2 > R1) {
valx[get(x2)] = 1; valx[get(x1)] = 0;
}
else {
merge(x1, x2);
}
}
Ex.pb(lsx[i].back());
int x = lsx[i].back();
if (valx[get(x)] == -1) valx[get(x)] = 1;
}
for (int u : vc) {
dfsx(u, v);
}
}
int oprx() {
int R = 0;
for (auto f : resx) {
int jx = f.F; int ux = E[jx].F, vx = E[jx].S;
if (get(ux) != get(vx)) {
Ex.pb(jx); merge(ux, vx); R += f.S;
}
}
return R;
}
int oprf(int v, int l, int r) {
Ex.clear();
iota(p, p + n, 0); fill(valx, valx + n, -1);
for (int i = l; i < r; i++) {
int j = adj[v][i].S;
int u = E[j].F, v = E[j].S;
Ex.pb(j); merge(u, v);
}
int R = oprx(); int res = askx() - R;
return res;
}
void calx(int v, int l, int r, int R) {
if (l >= r || R == 0) return ;
if (R == r - l) {
for (int i = l; i < r; i++) {
int j = adj[v][i].S;
ans.pb(j);
}
return ;
}
int mid = (l + r) / 2;
int R1 = oprf(v, l, mid), R2 = R - R1;
calx(v, l, mid, R1); calx(v, mid, r, R2);
}
vector<int> find_roads(int nx, vector<int> ux, vector<int> vx) {
n = nx; m = len(ux);
for (int i = 0; i < m; i++) {
int u = ux[i], v = vx[i];
if (u > v) swap(u, v);
adj[u].pb(Mp(v, i)); adj[v].pb(Mp(u, i));
E.pb(Mp(u, v));
}
iota(p, p + m, 0); fill(valx, valx + m, -1);
fill(M, M + n, 0); M[0] = 1; dfsx(0);
for (int j : Rx) resx.pb(Mp(j, valx[get(j)]));
for (int i = 0; i < n; i++) adj[i].clear();
for (int i = 0; i < m; i++) {
int u = E[i].F, v = E[i].S;
adj[u].pb(Mp(v, i));
}
for (int v = 0; v < n; v++) {
calx(v, 0, len(adj[v]), oprf(v, 0, len(adj[v])));
}
return ans;
}
