#include <iostream>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include "simurgh.h"
using namespace std;
int n,m;
vector<int> u,v;
vector<int> ans;
vector<int> e[505];
int id[505][505];
vector<int> tree_e;
int fa[505],idx,dfn[505],dfo[505];
bool in_Tree(int a,int b){//whether a is in b
	return (dfn[a]>=dfn[b]&&dfo[a]<=dfo[b]);
}
void dfs(int now,int f){
	fa[now]=f;
	dfn[now]=++idx;
	for (int i=0;i<(int)e[now].size();i++)
		if (e[now][i]!=f&&dfn[e[now][i]]==0){
			tree_e.push_back(id[e[now][i]][now]);
			dfs(e[now][i],now);
		}
	dfo[now]=idx;
	return;
}
int dsu[505];
int dsu_find(int x){
	if (x==dsu[x])return x;
	return dsu[x]=dsu_find(dsu[x]); 
} 
pair<vector<int>,int> get_tree(vector<int> id){
	int cnt=0;
	for (int i=0;i<n;i++)dsu[i]=i;
	for (int i=0;i<(int)id.size();i++){
		int x=dsu_find(u[id[i]]),y=dsu_find(v[id[i]]);
		dsu[y]=x;
	}
	for (int i=0;i<m;i++){
		if (ans[i]==-1)continue;
		int x=dsu_find(u[i]),y=dsu_find(v[i]);
		if (x!=y){
			id.push_back(i);
			cnt+=ans[i];
			dsu[y]=x;
		}
	}
	for (int i=0;i<m;i++){
		if (ans[i]!=-1)continue;
		int x=dsu_find(u[i]),y=dsu_find(v[i]);
		if (x!=y){
			id.push_back(i);
			cnt=-1;
			dsu[y]=x;
		}
	}
	return make_pair(id,cnt);
}
vector<int> del(vector<int> a,int x){
	vector<int> ans;
	for (int i=0;i<(int)a.size();i++)
		if (a[i]!=x)ans.push_back(a[i]);
	return ans;
}
vector<int> ins(vector<int> a,int x){
	vector<int> ans=a;
	ans.push_back(x);
	return ans;
}
void get_circle(vector<int> id,int c_id){
	int l=(int)id.size();
	vector<int> val(l);
	int x=-1,t=-1;
	for (int i=0;i<l;i++)
		if (ans[id[i]]!=-1)x=id[i];
	if (x!=-1){
		vector<int> qwq;
		if (x==c_id)qwq=tree_e;
		else qwq=ins(del(tree_e,x),c_id);
		t=count_common_roads(qwq)+ans[x];
	}
	else{
		int mn=n+1,mx=-1;
		for (int i=0;i<l;i++){
			vector<int> qwq;
			if (id[i]==c_id)qwq=tree_e;
			else qwq=ins(del(tree_e,id[i]),c_id);
			val[i]=count_common_roads(qwq);
			mn=min(mn,val[i]);
			mx=max(mx,val[i]);
		}
		if (mn==mx){
			for (int i=0;i<l;i++)ans[id[i]]=0;
		}
		else{
			for (int i=0;i<l;i++)
				if (val[i]==mn)ans[id[i]]=1;
				else ans[id[i]]=0;
		}
		return;
	}
	for (int i=0;i<l;i++)
		if (ans[id[i]]==-1){
			vector<int> qwq;
			if (id[i]==c_id)qwq=tree_e;
			else qwq=ins(del(tree_e,id[i]),c_id);
			ans[id[i]]=t-count_common_roads(qwq);
		}
	return;
}
void get_nei(vector<int> id){
	int l=(int)id.size();
	if (l==0)return;
	pair<vector<int>,int> qwq=get_tree(id);
	if (count_common_roads(qwq.first)==qwq.second)return;
	if (l==1){
		ans[id[0]]=1;
		return;
	}
	vector<int> id_l,id_r;
	for (int i=0;i<l/2;i++)id_l.push_back(id[i]);
	for (int i=l/2;i<l;i++)id_r.push_back(id[i]);
	get_nei(id_l);
	get_nei(id_r);
	return;
}
vector<int> find_roads(int _n,vector<int> _u,vector<int> _v){
	n=_n,m=(int)_u.size();
	u=_u,v=_v;
	ans.resize(m);
	for (int i=0;i<m;i++)ans[i]=-1;
	memset(id,-1,sizeof(id));
	for (int i=0;i<m;i++){
		e[u[i]].push_back(v[i]);
		e[v[i]].push_back(u[i]);
		id[u[i]][v[i]]=id[v[i]][u[i]]=i;
	}
	memset(fa,-1,sizeof(fa));
	dfs(0,-1);
	for (int i=1;i<n;i++){
		if (ans[id[fa[i]][i]]!=-1)continue;
		int x=-1,y=-1;
		for (int j=0;j<n&&x==-1;j++)
			if (in_Tree(fa[i],j)){
				for (int k=0;k<n&&x==-1;k++)
					if (in_Tree(k,i)&&(j!=fa[i]||k!=i)&&id[j][k]!=-1){
						x=j,y=k;
						break;
					}
			}
		if (x==-1)ans[id[fa[i]][i]]=1;
		else{
			int z=id[x][y];
			vector<int> qwq;
			qwq.push_back(z);
			while(y!=x)qwq.push_back(id[fa[y]][y]),y=fa[y];
			get_circle(qwq,z);
		}
	}
	for (int i=0;i<n;i++){
		vector<int> qwq;
		for (int j=0;j<n;j++)
			if (id[i][j]!=-1&&ans[id[i][j]]==-1)qwq.push_back(id[i][j]);
		get_nei(qwq);
	} 
	vector<int> qwq;
	for (int i=0;i<m;i++)
		if (ans[i]==1)qwq.push_back(i);
	return qwq;
}