#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=502;
int aresta[MAXN*MAXN][2];
vector<int> g[MAXN];
int rep[MAXN], tam[MAXN];
set<int> config, atual;
int n, m, tenho;
bool debug=0;
int find(int cur) {
if(rep[cur]==cur) return cur;
return rep[cur]=find(rep[cur]);
}
void une(int a, int b) {
a=find(a); b=find(b);
if(a==b) return;
if(tam[a]<tam[b]) swap(a, b);
rep[a]=b;
}
int query(set<int> &s) {
// if(debug){for(auto cur : config) printf("%d ", cur);}
int auxx[MAXN]; for(int i=0; i<n; i++) auxx[i]=rep[i];
for(int i=0; i<n; i++) rep[i]=i;
for(auto cur : s) une(aresta[cur][0], aresta[cur][1]);
bool ok=0;
for(int i=0; i<n; i++) if(find(i)!=find(0)) ok=1; //deu ruim
for(int i=0; i<n; i++) rep[i]=auxx[i];
if(ok) return MAXN;
vector<int> aux; for(auto cur : s) aux.push_back(cur);
return count_common_roads(aux);
}
void atualiza() {
for(int i=0; i<n; i++) rep[i]=i;
for(auto cur : config) {
int a=aresta[cur][0]; int b=aresta[cur][1];
atual.insert(cur);
une(a, b);
// if(debug) printf("tree:: %d %d // %d\n", a, b, cur);
}
for(int i=0; i<m; i++) {
int a=aresta[i][0]; int b=aresta[i][1];
if(find(a)==find(b)) continue;
atual.insert(i);
une(a, b);
// if(debug) printf("tree:: %d %d // %d\n", a, b, i);
}
tenho=query(atual);
}
bool testa(int ind) {
// for(auto cur : atual) printf("%d ", cur); cout << endl;
// printf("testa tirar %d\n", ind);
config.clear();
for(int i=0; i<n; i++) rep[i]=i;
for(auto cur : atual) {
if(cur==ind) continue;
int a=aresta[cur][0];
int b=aresta[cur][1];
une(a, b);
// printf(" une %d %d\n", a, b);
config.insert(cur);
}
for(int i=0; i<m; i++) {
if(i==ind) continue;
int a=aresta[i][0];
int b=aresta[i][1];
// printf(" tenta %d // %d %d // %d %d\n", i, a, b, find(a), find(b));
if(find(a)==find(b)) continue;
config.insert(i);
// printf(" testa colocar %d >> %d %d\n", i, tenho, query(config));
if(tenho<query(config)) {
atual.erase(ind);
atual.insert(i);
return 1;
}
config.erase(i);
}
return 0;
}
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++) {
int a=U[i]; int b=V[i];
aresta[i][0]=a; aresta[i][1]=b;
g[a].push_back(i);
g[b].push_back(i);
}
srand(time(0)+n+m);
for(int i=0; i<n; i++) rep[i]=i, tam[i]=i;
random_shuffle(tam, tam+n);
atualiza();
while(tenho<n-1) {
for(auto cur : atual) {
if(testa(cur)) {
atualiza();
break;
}
}
}
vector<int> respf; for(auto cur : atual) respf.push_back(cur);
// if(debug) for(auto cur : respf) printf("%d ", cur);
return respf;
}
