#include "simurgh.h"
#include <iostream>
#include <cmath>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn=505;
struct union_find{
int parent[maxn];
int sz[maxn];
union_find(){
for(int i=0; i<maxn; i++){
parent[i]=i;
sz[i]=1;
}
}
int find(int x){
if(parent[x]==x){
return x;
}
return find(parent[x]);
}
int update(int x, int y){
x=find(x);
y=find(y);
if(sz[x]>sz[y]){
swap(x, y);
}
sz[y]+=sz[x];
parent[x]=y;
return x;
}
bool query(int x, int y){
return find(x)==find(y);
}
};
union_find U;
vector < int > a, b;
stack < int > s;
int n;
vector < int > q;
bool napravi(int x){
if(x==(int)a.size()){
int par=U.find(0);
for(int i=0; i<n; i++){
if(par!=U.find(i)){
return 0;
}
}
int br=count_common_roads(q);
if(br==n-1){
return 1;
}
return 0;
}
if(napravi(x+1)){
return 1;
}
if(!U.query(a[x], b[x])){
q.push_back(x);
s.push(U.update(a[x], b[x]));
if(napravi(x+1)){
return 1;
}
U.sz[U.parent[s.top()]]-=U.sz[s.top()];
U.parent[s.top()]=s.top();
q.pop_back();
s.pop();
}
return 0;
}
vector < int > find_roads(int nn, vector < int > u, vector < int > v) {
a=u;
b=v;
n=nn;
napravi(0);
return q;
}
