#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
//int common = count_common_roads(r);
const int TAILLEMAXI=250, EN_COURS=1, FINI=2;
vector<int> adja[TAILLEMAXI];
vector<pair<int,int>> aretes;
int dejavu[TAILLEMAXI];
vector<int> cycle;
vector<int> pile;
vector<int> royal; /// 0=jsp, 1=oui, 2=non
bool stop;
vector<int> parent;
int trouver(int a){
if (parent[a]!=a){
parent[a]=trouver(parent[a]);
}
return parent[a];
}
void unir(int a, int b){
parent[trouver(a)]=parent[trouver(b)];
}
int autre(int num_ar, int ec){
if (ec==aretes[num_ar].first){
return aretes[num_ar].second;
}
return aretes[num_ar].first;
}
void dfs(int pos, int vient){
if (stop){
return ;
}
if (dejavu[pos]==FINI){
return ;
}
if (dejavu[pos]==EN_COURS){
cycle.push_back(pile.back());
pile.pop_back();
while (aretes[pile.back()].first!=pos and aretes[pile.back()].second!=pos){
cycle.push_back(pile.back());
pile.pop_back();
}
cycle.push_back(pile.back());
stop=true;
return ;
}
dejavu[pos]=EN_COURS;
for (auto a:adja[pos]){
if (a!=vient and royal[a]!=1){
pile.push_back(a);
dfs(autre(a, pos), a);
if (!stop){
pile.pop_back();
}
}
}
dejavu[pos]=FINI;
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
int nbaretes=u.size();
royal.resize(nbaretes);
for (int i=0;i<nbaretes;i++){
aretes.push_back({u[i], v[i]});
adja[u[i]].push_back(i);
adja[v[i]].push_back(i);
}
while (1>0){
cycle.clear();
pile.clear();
stop=false;
for (int i=0;i<n;i++){
dejavu[i]=0;
}
for (int i=0;i<n;i++){
dfs(i, -1);
}
/*for (auto c:cycle){
cout<<c<<" ";
}
cout<<endl;*/
if (cycle.empty()){
vector<int> rep;
for (int i=0;i<nbaretes;i++){
if (royal[i]!=1){
rep.push_back(i);
//cout<<i<<endl;
}
}
return rep;
}
parent.clear();
for (int i=0;i<n;i++){
parent.push_back(i);
}
for (auto a:cycle){
unir(aretes[a].first, aretes[a].second);
}
vector<int> encours;
for (int i=0;i<nbaretes;i++){
if (trouver(aretes[i].first)!=trouver(aretes[i].second)){
unir(aretes[i].first, aretes[i].second);
encours.push_back(i);
}
}
vector<int> val;
int val_min=TAILLEMAXI;
for (auto a:cycle){
for (auto x:cycle){
if (x!=a){
encours.push_back(x);
}
}
int v=count_common_roads(encours);
//cout<<v<<endl;
val.push_back(v);
val_min=min(val_min, v);
for (int i=0;i<(int)cycle.size()-1;i++){
encours.pop_back();
}
}
for (int i=0;i<(int)cycle.size();i++){
if (val[i]==val_min){
royal[cycle[i]]=2;
//cout<<"oui "<<cycle[i]<<endl;
}
else {
royal[cycle[i]]=1;
//cout<<"non "<<cycle[i]<<endl;
}
}
}
//return {0};
}
