#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=507;
vector<pair<int,int>>V[LIM];
vector<int>D;
pair<int,int>kraw[LIM*LIM];
int pre[LIM], mi[LIM], oc[LIM], jaki[LIM], drzewo[LIM*LIM], typ[LIM*LIM], F[LIM], lpre, n, m;
int licznik;
int fnd(int x) {
if(F[x]==x) return x;
return F[x]=fnd(F[x]);
}
bool uni(int a, int b) {
if(fnd(a)==fnd(b)) return false;
F[fnd(a)]=fnd(b);
return true;
}
void DFS(int x, int o) {
pre[x]=mi[x]=++lpre;
for(auto i : V[x]) if(i.st!=o) {
if(!pre[i.st]) {
oc[i.st]=x;
jaki[i.st]=i.nd;
drzewo[i.nd]=1;
DFS(i.st, x);
mi[x]=min(mi[x], mi[i.st]);
} else mi[x]=min(mi[x], pre[i.st]);
}
if(x && mi[x]==pre[x]) typ[jaki[x]]=1;
}
int cnt(vector<int>P) {
rep(i, n) F[i]=i;
for(auto i : P) uni(kraw[i].st, kraw[i].nd);
int sum=0;
for(auto i : D) if(uni(kraw[i].st, kraw[i].nd)) {
sum+=typ[i];
P.pb(i);
}
++licznik;
assert(licznik<=8000);
return count_common_roads(P)-sum;
}
void solve(vector<int>P, int k) {
if(!k) {
for(auto i : P) typ[i]=0;
return;
}
if(P.size()==k) {
for(auto i : P) typ[i]=1;
return;
}
int sr=(P.size()+1)/2;
vector<int>A, B;
rep(i, sr) A.pb(P[i]);
for(int i=sr; i<P.size(); ++i) B.pb(P[i]);
int x=cnt(A);
solve(A, x);
solve(B, k-x);
}
vector<int>find_roads(int _n, vector<int>_u, vector<int>_v) {
n=_n; m=_u.size();
rep(i, m) {
kraw[i]={_u[i], _v[i]};
if(kraw[i].st>kraw[i].nd) swap(kraw[i].st, kraw[i].nd);
V[kraw[i].st].pb({kraw[i].nd, i});
V[kraw[i].nd].pb({kraw[i].st, i});
typ[i]=-1;
}
DFS(0, 0);
rep(i, m) if(drzewo[i]) D.pb(i);
++licznik;
assert(licznik<=8000);
int x=count_common_roads(D);
rep(i, m) if(!drzewo[i]) {
int a=kraw[i].st, b=kraw[i].nd;
if(pre[a]<pre[b]) swap(a, b);
bool ok=false;
for(int j=a; j!=b; j=oc[j]) {
if(typ[jaki[j]]==-1) ok=true;
}
if(!ok) continue;
for(int j=a; j!=b; j=oc[j]) if(typ[jaki[j]]==-1) {
vector<int>T=D;
rep(l, T.size()) if(T[l]==jaki[j]) T[l]=i;
++licznik;
assert(licznik<=8000);
int y=count_common_roads(T);
if(x==y) typ[jaki[j]]=typ[i];
else if(x==y+1) {
typ[jaki[j]]=1;
typ[i]=0;
} else {
typ[jaki[j]]=0;
typ[i]=1;
}
}
if(typ[i]==-1) {
ok=false;
for(int j=a; j!=b; j=oc[j]) if(typ[jaki[j]]!=-1) {
vector<int>T=D;
rep(l, T.size()) if(T[l]==jaki[j]) T[l]=i;
++licznik;
assert(licznik<=8000);
int y=count_common_roads(T);
typ[i]=y-x+typ[jaki[j]];
ok=true;
break;
}
if(!ok) typ[i]=0;
}
for(int j=a; j!=b; j=oc[j]) if(typ[jaki[j]]==-1) typ[jaki[j]]=typ[i];
}
rep(i, n) {
vector<int>P;
rep(j, m) if(kraw[j].st==i || kraw[j].nd==i) P.pb(j);
solve(P, cnt(P));
}
vector<int>ans;
rep(i, m) if(typ[i]==1) ans.pb(i);
return ans;
}
