#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
const int Nmax=510, Kmax=Nmax*Nmax/2;
int N, M, p, u[Kmax], v[Kmax], par[Nmax], parc[Nmax], dep[Nmax], dfsn[Nmax], top[Nmax], low[Nmax], back[Nmax];
int total, chk[Kmax];
vector<pair<int, int>> adj[Nmax], adj2[Nmax];
vector<tuple<int, int, int>> tree;
vector<int> V;
int value(int x, int y) {
for(int &i:V) if(i==x) i=y;
int ret=count_common_roads(V);
for(int &i:V) if(i==y) i=x;
return ret;
}
int value2(vector<int> X) {
for(int i:X) {
if(dep[u[i]]<dep[v[i]]) swap(u[i], v[i]);
for(int &j:V) if(j==parc[u[i]]) j=i;
}
int ret=count_common_roads(V)-total;
for(int i:X) {
for(int &j:V) if(j==i) j=parc[u[i]], ret+=chk[parc[u[i]]];
}
return ret;
}
void DFS(int curr, int prev) {
dfsn[curr]=top[curr]=++p;
for(auto [next, c]:adj[curr]) if(next!=prev) {
if(dfsn[next]) {
if(top[curr]>dfsn[next]) top[curr]=dfsn[next], back[curr]=c, low[curr]=curr;
}
else {
par[next]=curr, parc[next]=c, dep[next]=dep[curr]+1;
tree.push_back({curr, next, c});
adj2[curr].push_back({next, c});
DFS(next, curr);
if(top[curr]>top[next]) top[curr]=top[next], back[curr]=back[next], low[curr]=low[next];
}
}
}
void DFS2(int curr) {
for(auto [next, c]:adj2[curr]) {
DFS2(next);
if(chk[c]!=-1) continue;
if(top[next]>dfsn[curr]) chk[c]=1;
else {
vector<int> tmp;
bool flag=false; int q=0;
for(int i=low[next]; dfsn[i]!=top[next]; i=par[i]) {
tmp.push_back(parc[i]);
if(chk[parc[i]]!=-1) flag=true, q=parc[i];
}
if(flag) {
chk[back[next]]=chk[q]+value(q, back[next])-total;
for(int i:tmp) if(chk[i]==-1) chk[i]=chk[back[next]]-value(i, back[next])+total;
}
else {
int X=total;
vector<int> Y;
for(int i:tmp) Y.push_back(value(i, back[next]));
bool flag2=false;
for(int i=0; i<Y.size(); i++) {
if(Y[i]==X+1) flag2=true, chk[back[next]]=1, chk[tmp[i]]=0;
else if(Y[i]==X-1) flag2=true, chk[back[next]]=0, chk[tmp[i]]=1;
}
if(flag2) {
for(int i=0; i<Y.size(); i++) if(Y[i]==X) chk[tmp[i]]=chk[back[next]];
}
else {
chk[back[next]]=false;
for(int i=0; i<Y.size(); i++) if(Y[i]==X) chk[tmp[i]]=false;
}
}
}
}
}
void F(int l, int r, int sum, vector<int> E) {
if(l==r) {
if(sum) chk[E[l]]=1;
else chk[E[r]]=0;
return;
}
if(l>r) return;
int m=(l+r)/2;
vector<int> tmp;
for(int i=l; i<=m; i++) tmp.push_back(E[i]);
int lsum=value2(tmp);
if(lsum) F(l, m, lsum, E);
if(sum-lsum) F(m+1, r, sum-lsum, E);
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
N=n, M=u.size();
for(int i=0; i<M; i++) {
::u[i]=u[i], ::v[i]=v[i];
adj[u[i]].push_back({v[i], i}), adj[v[i]].push_back({u[i], i});
}
for(int i=0; i<M; i++) chk[i]=-1;
DFS(0, -1);
for(auto [u, v, c]:tree) V.push_back(c);
total=count_common_roads(V);
DFS2(0);
for(int i=0; i<N; i++) {
vector<int> E;
for(auto [j, c]:adj[i]) if(dfsn[j]>dfsn[i] && !chk[c]) E.push_back(c);
if(!E.empty()) F(0, E.size()-1, value2(E), E);
}
for(int i=0; i<M; i++) if(chk[i]==-1) {
if(dep[u[i]]<dep[v[i]]) swap(u[i], v[i]);
chk[i]=chk[parc[u[i]]]+value(parc[u[i]], i)-total;
}
vector<int> ret;
for(int i=0; i<M; i++) if(chk[i]==1) ret.push_back(i);
return ret;
}
