/* name: simurgh
 * author: 5ab
 * created at: 2024-05-04
 */
#include <numeric>
#include <cstring>
#include <cassert>
#include <iostream>
#include <vector>
#include <queue>
#include "simurgh.h"
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))

auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };

using ll = long long;
const int N = 500;

bool vis[N], cov[N], gd[N], isa[N * N];
int n, dfn[N], ps[N], g[N][N], par[N], dsu[N], deg[N], ind = 0;
vector<int> tr[N];

void dfs(int id)
{
	vis[id] = 1;
	ps[dfn[id] = ind++] = id;
	for (int x = 0; x < n; x++)
		if (g[id][x] != -1 && !vis[x])
		{
			tr[id].push_back(x);
			par[x] = id;
			dfs(x);
		}
}
int fnd(int x) { return dsu[x] == x ? x : (dsu[x] = fnd(dsu[x])); }

vector<int> find_roads(int _n, vector<int> u, vector<int> v)
{
	n = _n;
	memset(g, -1, sizeof g);
	for (int i = 0; i < ssz(u); i++)
	{
		int x = u[i], y = v[i];
		g[x][y] = g[y][x] = i;
	}
	par[0] = -1, dfs(0);
	
	vector<int> rs(n - 1);
	for (int i = 1; i < n; i++)
		rs[i - 1] = g[par[i]][i];
	int bs = count_common_roads(rs);
	
	for (int i = n - 1; i >= 0; i--)
	{
		int x = ps[i], y = ps[i];
		for (int j = 0; j < i; j++)
			if (g[x][ps[j]] != -1)
			{
				y = ps[j];
				break;
			}
		if (x == y || y == par[x])
			continue;
		int rcx = -1, ev = g[x][y], mn = bs, mx = bs;
		vector<pair<int, int>> res;
		for (int z = x; z != y; z = par[z])
		{
			if (cov[z])
			{
				rcx = z;
				continue;
			}
			swap(ev, rs[z - 1]);
			int cv = count_common_roads(rs);
			res.emplace_back(z, cv);
			chmin(mn, cv), chmax(mx, cv);
			swap(ev, rs[z - 1]);
			cov[z] = 1;
		}
		// cerr << x << " " << y << "  " << mn << " " << mx << endl;
		if (mn == mx && rcx != -1)
		{
			swap(ev, rs[rcx - 1]);
			chmax(mx, gd[rcx] + count_common_roads(rs));
			swap(ev, rs[rcx - 1]);
		}
		for (auto [z, vv] : res)
		{
			gd[z] = mx - vv;
			// cerr << z << " " << mx - vv << endl;
		}
	}
	vector<int> ans;
	for (int i = 1; i < n; i++)
		if (!cov[i])
		{
			gd[i] = 1, isa[g[i][par[i]]] = 1;
			ans.push_back(g[i][par[i]]);
		}
	
	// for (int i = 1; i < n; i++)
	// 	cerr << i << " " << par[i] << " " << g[i][par[i]] << " " << gd[i] << endl;
	
	// cerr << "ok" << endl;
	
	vector<pair<int, int>> edges;
	auto doq = [&]()
	{
		iota(dsu, dsu + n, 0);
		int rd = 0;
		rs.clear();
		for (auto [x, y] : edges)
		{
			rd += isa[g[x][y]];
			dsu[fnd(x)] = fnd(y);
			rs.push_back(g[x][y]);
		}
		for (int j = 1; j < n; j++)
		{
			int x = fnd(j), y = fnd(par[j]);
			if (x != y)
			{
				dsu[x] = y;
				rd += gd[j];
				rs.push_back(g[j][par[j]]);
			}
		}
		assert(ssz(rs) == n - 1);
		// cerr << ssz(rs) << endl;
		return count_common_roads(rs) - rd;
	};
	
	queue<int> q;
	for (int i = 0; i < n; i++)
	{
		edges.clear();
		for (int j = 0; j < n; j++)
			if (g[i][j] != -1)
				edges.emplace_back(i, j);
		deg[i] = doq();
		if (deg[i] == 1)
			q.push(i);
		// cerr << deg[i] << endl;
	}
	// for (int x : ans)
	// 	cerr << x << " ";
	// cerr << endl;
	while (!q.empty())
	{
		int id = q.front(); q.pop();
		if (deg[id] == 0)
			continue;
		edges.clear();
		for (int j = 0; j < n; j++)
			if (g[id][j] != -1 && !isa[g[id][j]])
				edges.emplace_back(id, j);
		// cerr << id << " " << deg[id] << " " << ssz(edges) << " ";
		vector<pair<int, int>> rest;
		while (ssz(edges) > 1)
		{
			int ms = ssz(edges) / 2;
			rest.assign(edges.begin() + ms, edges.end());
			edges.resize(ms);
			if (!doq())
				rest.swap(edges);
		}
		int ac = edges[0].second;
		isa[g[id][ac]] = 1;
		ans.push_back(g[id][ac]);
		if (--deg[ac] == 1)
			q.push(ac);
		// cerr << ac << " " << deg[ac] << endl;
	}
	// for (int x : ans)
	// 	cerr << x << " ";
	// cerr << endl;
	return ans;
}
// started coding at: 05-04 22:12:33