#include "simurgh.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> pi;
vector<pi> nei[100];
int parent[500];
int size[500];
void init(int n){
for(int i=0;i<n;i++){
size[i]=1;parent[i]=i;
}
}
int root(int a){
if(parent[a]==a)return a;
return root(parent[a]);
}
void merge(int a, int b){/*cout<<a<<" "<<b<<endl;
for(int i=0;i<7;i++)cout<<parent[i]<<" ";
cout<<endl;
for(int i=0;i<7;i++)cout<<size[i]<<" ";
cout<<endl<<endl;*/
a=root(a);
b=root(b);
if(a==b)return;
if(size[a]<size[b]){
parent[a]=b;
size[b]+=size[a];
return;
}
parent[b]=a;
size[a]+=size[b];
}
bool samecomponent(int a, int b){/*cout<<a<<" "<<b<<endl;
for(int i=0;i<7;i++)cout<<parent[i]<<" ";
cout<<endl;
for(int i=0;i<7;i++)cout<<size[i]<<" ";
cout<<endl<<endl;*/
a=root(a);
b=root(b);
if(a==b)return true;
return false;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
vector<pair<int,int> >nei[n];
for(int i=0;i<u.size();i++){
nei[u[i]].push_back(pair<int,int>(v[i],i));
nei[v[i]].push_back(pair<int,int>(u[i],i));
}
int ans[u.size()];
for(int i=0;i<u.size();i++)ans[i]=-1;
vector<pair<int,int> >tree[n];
init(n);
bool istree[u.size()];
vector<int> maintree;
for(int i=0;i<u.size();i++){istree[i]=false;
if(!samecomponent(u[i],v[i])){istree[i]=true;
merge(u[i],v[i]);
tree[u[i]].push_back(pair<int,int>(v[i],i));
tree[v[i]].push_back(pair<int,int>(u[i],i));
//cout<<i<<endl;
maintree.push_back(i);
}
}
int s=count_common_roads(maintree);
for(int i=0;i<u.size();i++){
if(!istree[i]){
queue<int> q;
int dist[n];
for(int i=0;i<n;i++)dist[i]=-1;
dist[u[i]]=0;
q.push(u[i]);
while(!q.empty()){
int node=q.front();q.pop();
for(int j=0;j<tree[node].size();j++){
int V=tree[node][j].first;
if(dist[V]==-1){
dist[V]=dist[node]+1;
q.push(V);
}
}
}
vector<int> edges;
int pnt=v[i];
while(dist[pnt]!=0){
for(int j=0;j<tree[pnt].size();j++){
int node=tree[pnt][j].first;
if(dist[node]<dist[pnt]){
edges.push_back(tree[pnt][j].second);
pnt=node;
j=10000;
}
}
}//OK
/*cout<<"Edge no "<<i<<" : ";
for(int j=0;j<edges.size();j++)cout<<edges[j]<<" ";
cout<<endl;*/
vector<int> indeterminado;
vector<int> determinado;
for(int j=0;j<edges.size();j++){
if(ans[edges[j]]==-1)indeterminado.push_back(edges[j]);
else determinado.push_back(edges[j]);
}
if(determinado.size()==0){
vector<pair<int,int> >respostas;
for(int j=0;j<edges.size();j++){
int lo,hi;
lo=-1;
hi=n;
while(hi-lo>1){
int mid=(hi+lo)/2;
if(maintree[mid]<edges[j])lo=mid;
else hi=mid;
}
maintree[hi]=i;
int A=count_common_roads(maintree);
respostas.push_back(pair<int,int>(A,edges[j]));
maintree[hi]=edges[j];
}
respostas.push_back(pair<int,int>(s,i));
sort(respostas.begin(),respostas.end());
/*for(int j=0;j<respostas.size();j++){
cout<<respostas[j].first<<" ";
}cout<<endl;
for(int j=0;j<respostas.size();j++){
cout<<respostas[j].second<<" ";
}cout<<endl;*/
if(respostas[0].first==respostas[respostas.size()-1].first){
for(int j=0;j<respostas.size();j++){
ans[respostas[j].second]=0;
}
}else{
for(int j=0;j<respostas.size();j++){ans[respostas[j].second]=0;
if(respostas[j].first==respostas[0].first){
ans[respostas[j].second]=1;
}
}
}
}else{
vector<pair<int,int> >respostas;
for(int j=0;j<indeterminado.size();j++){//cout<<indeterminado[j]<<" "<<ans[indeterminado[j]]<<endl;
int lo,hi;
lo=-1;
hi=n;
while(hi-lo>1){
int mid=(hi+lo)/2;
if(maintree[mid]<indeterminado[j])lo=mid;
else hi=mid;
}//cout<<maintree[hi]<<" "<<indeterminado[j]<<endl;
maintree[hi]=i;
/*for(int i=0;i<n-1;i++){
cout<<maintree[i]<<" ";
}cout<<endl;*/
int A=count_common_roads(maintree);
//cout<<A<<endl;
respostas.push_back(pair<int,int>(A,indeterminado[j]));
maintree[hi]=indeterminado[j];
}//cout<<endl;
respostas.push_back(pair<int,int>(s,i));
//cout<<determinado[0]<<" "<<indeterminado.size()<<endl;
int lo,hi;
lo=-1;
hi=n;
while(hi-lo>1){
int mid=(hi+lo)/2;
if(maintree[mid]<determinado[0])lo=mid;
else hi=mid;
}
maintree[hi]=i;
int reference=count_common_roads(maintree);
maintree[hi]=determinado[0];
for(int j=0;j<respostas.size();j++){//cout<<respostas[j].first<<" "<<respostas[j].second<<endl;
ans[respostas[j].second]=ans[determinado[0]]+reference-respostas[j].first;
}
}
}
/*cout<<i<<endl;
for(int i=0;i<u.size();i++){
cout<<ans[i]<<" ";
}cout<<endl;
for(int i=0;i<n-1;i++){
cout<<maintree[i]<<" ";
}cout<<endl;*/
}
/*for(int i=0;i<u.size();i++){
cout<<ans[i]<<" ";
}cout<<endl;*/
vector<int> r;
for(int i=0;i<u.size();i++){
if(ans[i]!=0)r.push_back(i);
}
return r;
}
