#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = 500;
const int M = N * (N - 1) / 2;
vector<pii> T[N];
vector<pii> Q[N];
int dep[N];
pii low[N];
int in[N];
int edge[M];
int know[M];
vector<int> fq;
void dfs(int u, int pp){
low[u] = mp(dep[u], -1);
for(auto x : T[u]){
if(x.fi == pp) continue;
if(dep[x.fi] == -1){
in[x.fi]=x.se;
dep[x.fi]=dep[u]+1;
dfs(x.fi, u);
fq.push_back(x.se);
low[u] = min(low[u], low[x.fi]);
if(dep[u] < low[x.fi].fi){
know[x.se] = 1;
edge[x.se] = -1; // bridge
}
else{
edge[x.se] = 0; //
}
}
else{
edge[x.se] = 2; // these f*ck everything up
low[u] = min(low[u], mp(dep[x.fi], x.se));
}
}
}
vector<int> G[M];
int get(int ii, int jj){
vector<int> aq;
for(auto x : fq) if(x != ii) aq.push_back(x);
aq.push_back(jj);
return count_common_roads(aq);
}
vector<int> cyc;
bool vis[M];
void dfs1(int u){
vis[u]=true;
cyc.push_back(u);
for(auto x : G[u]){
if(!vis[x]){
dfs1(x);
}
}
}
int par[N];
int fin_node(int x){
if(par[x] == x) return x;
return par[x]=fin_node(par[x]);
}
bool unite(int a, int b){
a = fin_node(a);
b = fin_node(b);
if(a == b) return false;
par[a] = b;
return true;
}
int n;
vector<pii> saf;
vector<int>u,v;
int bins(int l, int r, int val){
if(val == -1){
vector<int> E;
for(int i = 0 ; i < n; i ++ ){
par[i]=i;
}
int rem = 0;
for(int j = l ; j <= r; j ++ ){
E.push_back(saf[j].se);
unite(u[saf[j].se], v[saf[j].se]);
}
for(auto x : fq){
if(unite(u[x], v[x])){
rem += know[x];
E.push_back(x);
}
}
val = count_common_roads(E) - rem;
}
if(val == 0) return 0;
if(l == r){
know[saf[l].se]=1;
return val;
}
int mid = (l + r) / 2;
int lef = bins(l, mid, -1);
bins(mid + 1, r, val - lef);
return val;
}
vector<int> find_roads(int _n, vector<int> u_, vector<int> v_) {
n = _n;
u = u_;
v = v_;
int m = u.size();
for(int i = 0 ; i < m ; i ++ ){
T[u[i]].push_back(mp(v[i], i));
T[v[i]].push_back(mp(u[i], i));
edge[i] = -1;
know[i]=-1;
}
for(int i = 0 ; i < n; i ++ ){
dep[i] = -1;
}
dep[0]=0;
dfs(0,-1);
for(int i = 0 ; i < m ; i ++) {
if(dep[u[i]] > dep[v[i]])
swap(u[i], v[i]);
}
for(int i = 1; i < n; i ++ ){
edge[low[i].se] = 1;
}
int faf = count_common_roads(fq);
int nw;
int uu, vv;
int go;
for(int i = 0 ; i < m ; i ++ ){
if(edge[i] == 0){
uu = i;
vv = low[v[i]].se;
nw = get(uu, vv);
if(faf == nw){
G[uu].push_back(vv);
G[vv].push_back(uu);
}
else{
if(nw > faf){
know[vv]=1;
know[uu]=0;
}
else{
know[vv]=0;
know[uu]=1;
}
}
}
else if(edge[i] == 1){
vv = i;
go = v[i];
while(u[in[go]] != u[i]){
go = u[in[go]];
}
uu = in[go];
nw = get(uu, vv);
if(faf == nw){
G[uu].push_back(vv);
G[vv].push_back(uu);
}
else{
if(nw > faf){
know[vv]=1;
know[uu]=0;
}
else{
know[vv]=0;
know[uu]=1;
}
}
}
}
int val;
for(int i = 0 ; i < m ; i ++ ){
if(edge[i] == 0 || edge[i] == 1){
if(!vis[i]){
cyc.clear();
dfs1(i);
val = -1;
for(auto x : cyc){
if(know[x] != -1) val = know[x];
}
if(val == -1) val = 0;
for(auto x : cyc) know[x] = val;
}
}
}
vector<int> soln;
for(int i = 0 ; i < m ; i ++ ){
if(edge[i] == 2){
Q[u[i]].push_back(mp(v[i], i));
}
}
int cnt;
int cur;
for(int i = 0 ; i < n; i ++ ){
if(Q[i].empty()) continue;
saf = Q[i];
bins(0, (int)saf.size() - 1, -1);
}
for(int i = 0 ; i < m ; i ++ ){
if(know[i] == 1) soln.push_back(i);
}
return soln;
}
