#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
int id[505][505];
vector<int> con[505],con_luate[505];
int visited[505],pas;
bool isbun[250005],isbad[250005],isluat[250005];
vector<int> luate;
void dfs(int nod)
{
visited[nod]=pas;
for(int adj:con[nod])
{
if(visited[adj]!=pas)
{
luate.push_back(id[nod][adj]);
isluat[id[nod][adj]]=1;
con_luate[nod].push_back(adj);
con_luate[adj].push_back(nod);
dfs(adj);
}
}
}
vector<int> comp;
void dfs2(int nod, int interzis)
{
comp.push_back(nod);
visited[nod]=pas;
for(int adj:con_luate[nod])
{
if(adj!=interzis && visited[adj]!=pas)
{
dfs2(adj,interzis);
}
}
}
void sterge_luate(int u, int v)
{
for(int i=0;i<con_luate[u].size();i++)
{
if(con_luate[u][i]==v)
{
con_luate[u].erase(con_luate[u].begin()+i);
break;
}
}
for(int i=0;i<con_luate[v].size();i++)
{
if(con_luate[v][i]==u)
{
con_luate[v].erase(con_luate[v].begin()+i);
break;
}
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v)
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
id[i][j] = -1;
for(int i=0;i<u.size();i++)
{
id[u[i]][v[i]] = id[v[i]][u[i]] = i;
con[u[i]].push_back(v[i]);
con[v[i]].push_back(u[i]);
}
pas++;
dfs(0);
while(1)
{
int init = count_common_roads(luate);
if(init==n-1)
return luate;
for(int i=0;i<luate.size();i++)
{
if(isbun[luate[i]])
continue;
int a = u[luate[i]], b = v[luate[i]];
comp.clear();
pas++;
dfs2(a,b);
vector<int> ca = comp;
vector<bool> is_ca(n,0);
for(int x:ca)
is_ca[x]=1;
int care = -1;
bool gasit=0;
for(int j=0;j<u.size();j++)
{
if(!isluat[j] && !isbad[j] && is_ca[u[j]] != is_ca[v[j]])
{
int prec = luate[i];
luate[i] = j;
int newv = count_common_roads(luate);
luate[i] = prec;
if(newv == init + 1)
{
sterge_luate(u[luate[i]], v[luate[i]]);
con_luate[u[j]].push_back(v[j]);
con_luate[v[j]].push_back(u[j]);
isluat[luate[i]] = 0;
isluat[j] = 1;
isbad[luate[i]] = 1;
isbun[j] = 1;
luate[i] = j;
gasit = 1;
break;
}
else if(newv == init - 1)
{
isbun[luate[i]] = 1;
isbad[j] = 1;
gasit = 1;
break;
}
else
{
assert(newv==init);
care = j;
}
}
}
if(!gasit)
{
if(care==-1)
{
isbun[luate[i]] = 1;
///toate j urile care o ajuns in ifu de mai sus sunt bune----------------------------------------------
}
else
{
sterge_luate(u[luate[i]], v[luate[i]]);
con_luate[u[care]].push_back(v[care]);
con_luate[v[care]].push_back(u[care]);
isluat[luate[i]] = 0;
isluat[care] = 1;
luate[i] = care;
}
}
}
}
}
