#include <bits/stdc++.h>
using namespace std;
#include "simurgh.h"
//int count_common_roads(vector<int> r);
struct Arc {
int u, v, i;
};
int nbNodes, nbArcs;
vector<Arc> arcs;
vector<Arc> adj[501];
map<pair<int, int>, int> idx;
bool vu[501];
set<int> roads;
int oldValue = -1;
int query() {
vector<int> quer;
for(int i : roads) quer.push_back(i);
return oldValue = count_common_roads(quer);
}
void traverse(int u, int i) {
if(vu[u]) return;
vu[u] = 1;
if(i != -1) roads.insert(i);
for(Arc a : adj[u])
if(!vu[a.v])
traverse(a.v, a.i);
}
void buildTree() {
for(int i = 0; i < nbNodes; i++) vu[i] = false;
traverse(0, -1);
}
int parent[501*250];
int find(int x) {
return x == parent[x] ? x : (parent[x] = find(parent[x]));
}
void merge(int x, int y) {
parent[find(x)] = find(y);
}
const int ROYAL = 500*250+1;
const int BAD = 500*250+2;
bool good(int i) {
return find(i) == find(ROYAL);
}
bool bad(int i) {
return find(i) == find(BAD);
}
void init() {
for(int i = 0; i < nbArcs; i++) parent[i] = i;
parent[ROYAL] = ROYAL;
parent[BAD] = BAD;
}
vector<int> path, curr;
bool found=0;
void dfs(int u, int target, int p) {
if(u == target) {
found=1;
path = curr;
}
if(found) return;
for(Arc a : adj[u]) {
if(!roads.count(a.i) or a.v == p) continue;
curr.push_back(a.i);
dfs(a.v, target, u);
curr.pop_back();
}
}
vector<int> findCycle(int u, int v) {
path.clear(), curr.clear(), found=0;
dfs(u, v, -1);
return path;
}
void findSol() {
init();
for(Arc a : arcs) {
if(roads.count(a.i)) continue;
if(bad(a.i)) continue;
int i = a.i;
int u = a.u;
int v = a.v;
vector<int> cycle = findCycle(u, v);
for(int id : cycle) {
int old = oldValue;
roads.insert(i);
roads.erase(id);
int nouv = query();
if(nouv > old) {
merge(ROYAL, i);
merge(BAD, id);
break;
}
else if(nouv == old) {
merge(id, i);
roads.insert(id);
roads.erase(i);
oldValue = old;
}
else {
merge(id, ROYAL);
merge(i, BAD);
roads.insert(id);
roads.erase(i);
oldValue = old;
break;
}
}
}
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
nbNodes = n;
nbArcs = (int)u.size();
arcs.clear();
for(int i = 0; i < nbArcs; i++) {
arcs.push_back({u[i], v[i], i});
adj[u[i]].push_back({u[i], v[i], i});
adj[v[i]].push_back({v[i], u[i], i});
}
vector<int> ans;
buildTree();
query();
findSol();
for(int i : roads) ans.push_back(i);
return ans;
}
/*
bool GOLDEN[501*250];
int count_common_roads(vector<int> r) {
int cnt(0);
for(int i:r)if(GOLDEN[i])cnt++;
return cnt;
}
int main() {
int T=1;
while(T--){
int n, m;cin>>n>>m;
vector<int>u(m), v(m);
for(int i=0;i<m;i++){
cin>>u[i]>>v[i];
}
for(int i=0;i<m;i++)GOLDEN[i]=0;
for(int i=0;i<n-1;i++){int s;cin>>s;GOLDEN[s]=1;}
vector<int> sol = find_roads(n, u, v);
for(int i : sol) {
cout << i << " ";
}
cout << endl;
}
}
*/
