#include<bits/stdc++.h>
#include "simurgh.h"
using namespace std;
const int MAX_SOM=500+5,MAX_ARE=500*500+5;
int nbSom,nbAre,valGlob,nbQuest=1,verifRest,prevu;
vector<int> debAre,finAre;
vector<pair<int,int>> adja[MAX_SOM];
int prof[MAX_SOM];
int pere[MAX_SOM][2];
int etat[MAX_ARE],pris[MAX_ARE];
int degRest[MAX_SOM];
int pereUF[MAX_SOM];
vector<int> arbreInit,arcRem,chem,pareil;
vector<int> quest;
void DFS(int pos,int profCour,int anci,int numAre) {
if (prof[pos]==0) {
prof[pos]=profCour;
pere[pos][0]=anci;
pere[pos][1]=numAre;
for (auto i:adja[pos]) {
if (prof[i.first]==0) {
arbreInit.push_back(i.second);
DFS(i.first,profCour+1,pos,i.second);
}
else if (prof[pos]>prof[i.first]+1) {
arcRem.push_back(i.second);
}
}
}
}
int askQuest(int nouvAre) {
nbQuest++;
quest={nouvAre};
for (int i:arbreInit) {
if (pris[i]==1) {
quest.push_back(i);
}
}
return count_common_roads(quest);
}
void afficher(vector<int> v) {
for (int i:v) {
cout<<i<<" ";
}
cout<<endl;
}
void init() {
for (int i=0;i<nbSom;i++) {
pereUF[i]=i;
}
quest.clear();
prevu=0;
}
int find(int pos) {
if (pereUF[pos]!=pos) {
pereUF[pos]=find(pereUF[pos]);
}
return pereUF[pos];
}
void unir(int idAre,int typeAre) {
int deb=debAre[idAre],fin=finAre[idAre];
if (find(deb)!=find(fin)) {
quest.push_back(idAre);
pereUF[find(deb)]=find(fin);
if (typeAre==1 and etat[idAre]==1) {
prevu++;
}
}
}
vector<int> find_roads(int n,vector<int> u,vector<int> v) {
nbSom=n;
debAre=u;
finAre=v;
nbAre=u.size();
for (int i=0;i<nbAre;i++) {
adja[debAre[i]].push_back(make_pair(finAre[i],i));
adja[finAre[i]].push_back(make_pair(debAre[i],i));
}
DFS(0,1,0,0);
//afficher(arbreInit);
//afficher(arcRem);
for (int i:arbreInit) {
pris[i]=1;
}
valGlob=count_common_roads(arbreInit);
int pos=0,ans;
for (int i:arcRem) {
chem.clear();
if (prof[finAre[i]]<prof[debAre[i]]) {
swap(finAre[i],debAre[i]);
}
pos=finAre[i];
verifRest=0;
while (pos!=debAre[i]) {
chem.push_back(pere[pos][1]);
if (etat[pere[pos][1]]==0) {
verifRest=1;
}
pos=pere[pos][0];
}
if (verifRest==1) {
pareil.clear();
for (int j:chem) {
if (etat[i]==0 or etat[j]==0) {
pris[j]=0;
ans=askQuest(i);
pris[j]=1;
if (valGlob<ans) {
etat[i]=1;
etat[j]=2;
}
else if (valGlob>ans) {
etat[j]=1;
etat[i]=2;
}
else {
if (etat[i]==etat[j]) {
pareil.push_back(j);
}
else {
if (etat[i]==0) {
etat[i]=etat[j];
}
else {
etat[j]=etat[i];
}
}
}
}
}
if (etat[i]==0) {
etat[i]=2;
}
for (int j:pareil) {
etat[j]=etat[i];
}
}
}
for (int i:arbreInit) {
if (etat[i]==0) {
etat[i]=1;
}
//cout<<i<<" : "<<etat[i]<<endl;
}
for (int i=0;i<nbSom;i++) {
init();
for (auto j:adja[i]) {
unir(j.second,0);
}
for (int j:arbreInit) {
unir(j,1);
}
ans=count_common_roads(quest);
nbQuest++;
degRest[i]=ans-prevu;
//cout<<i<<" "<<degRest[i]<<endl;
}
vector<int> repOr;
vector<pair<int,int>> nouvVec;
int deb,fin,mid,nouvAre;
for (int loop=0;loop<nbSom-1;loop++) {
for (int i=0;i<nbSom;i++) {
if (degRest[i]==1) {
pos=i;
}
}
deb=0;
fin=adja[pos].size()-1;
while (deb!=fin) {
mid=(deb+fin)/2;
init();
for (int i=deb;i<=mid;i++) {
unir(adja[pos][i].second,0);
}
for (int j:arbreInit) {
unir(j,1);
}
ans=count_common_roads(quest)-prevu;
nbQuest++;
if (ans>=1) {
fin=mid;
}
else {
deb=mid+1;
}
}
nouvAre=adja[pos][deb].second;
//cout<<nouvAre<<endl;
repOr.push_back(nouvAre);
deb=debAre[nouvAre];
fin=finAre[nouvAre];
degRest[deb]--;
degRest[fin]--;
nouvVec.clear();
for (auto j:adja[deb]) {
if (j!=make_pair(fin,nouvAre)) {
nouvVec.push_back(j);
}
}
adja[deb]=nouvVec;
nouvVec.clear();
for (auto j:adja[fin]) {
if (j!=make_pair(deb,nouvAre)) {
nouvVec.push_back(j);
}
}
adja[fin]=nouvVec;
}
//cout<<nbQuest<<endl;
return repOr;
}
