#include "simurgh.h"

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

namespace {
	const int N = 505, M = N * N;

	int A[M], B[M], m, n, fa[N], d[N], fw[N], ID[N][N]; 
	
	int st[M];
	
	vector<PII> g[N], e[N];
	
	bool vis[N], tr[M];
}

void dfs0(int u) {
	vis[u] = 1;
	for (PII o: g[u]) {
		int v = o.fi;
		if (!vis[v]) {
			d[v] = d[u] + 1;
			fa[v] = u; fw[v] = o.se;
			e[u].pb(o);
			tr[o.se] = 1;
			dfs0(v);
		}
	}
}

// w era p : Qry

int f[N];

int find(int x) {
	return x == f[x] ? x : f[x] = find(f[x]);
}

int ct = 0;

bool mg(int x, int y) {
	if (find(x) == find(y)) return 0;
	f[find(x)] = find(y);
	return 1;
}

int calc(vector<int> w, int p) {
	for (int i = 0; i < n; i++) f[i] = i;
	vector<int> s;
	for (int v: w) {
		if (v != p) {
			assert(mg(A[v], B[v]));
			s.pb(v);
		}
	}
	for (int i = 1; i < n; i++) {
		int x = fa[i], y = i;
		if (mg(x, y)) s.pb(fw[i]);
	}
	assert(s.size() == n - 1);
	++ct;
	return count_common_roads(s);
}

// get state: edge of cycle 

vector<int> get(vector<int> w) {
	int p = -1; int hv = 0;
	vector<int> ret(w.size(), 0);
	for (int i = 0; i < w.size(); i++) {
		int v = w[i];
		if (st[v] != -1) p = v, ret[i] = st[v]; 
		if (st[v] == -1) hv = 1;
	}
	if (!hv) return ret;
	if (p != -1) {
		int now = st[p], F = calc(w, p); // t + a[v]
		for (int i = 0; i < w.size(); i++) {
			int v = w[i];
			if (st[v] == -1) {
				int G = calc(w, v);
				// t + a[p]
				ret[i] = F - G + now;
			}
		}
		return ret;
	} else {
		int len = w.size();
		vector<int> e(len, 0);
		int sum = 0;
		for (int i = 0; i < len; i++) {
			int v = w[i];
			e[i] = calc(w, v);
			sum += e[i];
		}
		// sum = len * t + \sum a * (len - 1)
		int t = 0, sa = 0;
		if (sum % len) {
			sa = len - (sum % len);
			t = (sum - (len - 1) * sa) / len;
			for (int i = 0; i < len; i++) {
				int z = e[i] - t;
				ret[i] = sa - z;
			}
			return ret;
		} else {
			// all 0
			return ret; 
		}
	}
}

void inline fl(int w, int x, int y) {
	if (d[x] < d[y]) swap(x, y);
	// x jp y
	int p = x;
	vector<int> z; z.pb(w);
	bool ok = 0;
	while (p != y) {
		z.pb(fw[p]);
		if (st[fw[p]] == -1) ok = 1;
		p = fa[p];		
	}
	if (!ok) return;
	vector<int> S = get(z);
	for (int i = 0; i < z.size(); i++) {
		int u = z[i];
		if (~st[u]) {
			assert(st[u] == S[i]);
			continue;
		}
		st[u] = S[i];
	}
}

void inline fd() {
	dfs0(0);
	for (int i = 0; i < m; i++) {
		if (tr[i]) continue;
		fl(i, A[i], B[i]);
	}
	for (int i = 1; i < n; i++) {
		int u = fw[i];
		if (st[u] == -1) st[u] = 1;
	}
}

bool ask(int u, int l, int r) {
	for (int i = 0; i < n; i++) f[i] = i;
	int sm = 0;
	vector<int> z;
	for (PII o: g[u]) {
		int v = o.fi;
		if (v >= l && v <= r) {
			assert(mg(u, v));
			z.pb(o.se);
		}
	}
	for (int i = 1; i < n; i++) {
		if (mg(fa[i], i))
			sm += st[fw[i]], z.pb(fw[i]);
	}
	++ct;
	return count_common_roads(z) > sm;
}

void inline solve() {
	for (int i = 0; i < n; i++) {
		int p = i + 1;
		while (p < n) {
			if (!ask(i, p, n - 1)) break;
			int l = p, r = n - 1;
			while (l < r) {
				int mid = (l + r) >> 1;
				if (ask(i, p, mid)) r = mid;
				else l = mid + 1;
			}
			int u = ID[i][r];
			assert(u != -1);
			st[u] = 1;
			p = r + 1;
		}
	}
}

std::vector<int> find_roads(int z, std::vector<int> u, std::vector<int> v) {
	n = z, m = u.size();
	memset(ID, -1, sizeof ID);
	for (int i = 0; i < m; i++) A[i] = u[i], B[i] = v[i], ID[A[i]][B[i]] = ID[B[i]][A[i]] = i, g[A[i]].pb(mp(B[i], i)), g[B[i]].pb(mp(A[i], i));
	memset(st, -1, sizeof st);
	fd();
	solve();
	vector<int> r;
	for (int i = 0; i < m; i++) if (st[i] == -1) st[i] = 0;
	for (int i = 0; i < m; i++) if (st[i] == 1) r.pb(i);
	assert(r.size() == n - 1);
	return r;
}