#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 10;
struct EDGE{
int to , id;
};
int n , m , col[N];
vector <EDGE> adj[N];
vector <int> r;
bool marked[N] , dead[N] , vis[N];
void Dfs(int v)
{
marked[v] = true;
for(auto u : adj[v]) if(!marked[u.to] && !dead[u.to])
{
r.push_back(u.id);
col[u.to] = col[v];
Dfs(u.to);
}
}
vector<int> find_roads(int nn, vector<int> u, vector<int> v) {
n = nn;
m = u.size();
for(int i = 0 ; i < m ; i++)
{
adj[u[i]].push_back({v[i] , i});
adj[v[i]].push_back({u[i] , i});
}
int star = 0;
vector <int> cand;
dead[star] = true;
cand.push_back(star);
vector <int> cor;
while(!cand.empty())
{
vector <EDGE> add;
r = cor;
for(int i = 0 ; i < n ; i++)
{
marked[i] = false;
vis[i] = false;
}
int coco = 0;
for(int i = 0 ; i < n ; i++) if(!dead[i] && !marked[i])
{
col[i] = coco;
Dfs(i);
coco++;
}
for(int asd = 0 ; asd < coco ; asd++)
{
int mx = 0;
vector <EDGE> fake;
for(int i = 0 ; i < coco ; i++)
vis[i] = false;
for(auto v : cand) for(auto u : adj[v]) if(!dead[u.to] && col[u.to] != asd && !vis[col[u.to]])
{
r.push_back(u.id);
vis[col[u.to]] = true;
}
for(auto v : cand) for(auto u : adj[v]) if(!dead[u.to] && col[u.to] == asd)
{
r.push_back(u.id);
int now = count_common_roads(r);
if(now > mx)
{
mx = now;
fake.clear();
}
if(now == mx)
fake.push_back(u);
r.pop_back();
}
for(int i = 0 ; i < coco - 1 ; i++)
r.pop_back();
for(auto u : fake)
add.push_back(u);
}
cand.clear();
for(auto u : add)
{
cor.push_back(u.id);
dead[u.to] = true;
cand.push_back(u.to);
}
}
return cor;
}
