#include "simurgh.h"
#include <set>
#include <algorithm>
#include <cassert>
#include <random>
#include <ctime>
using namespace std;
const int MAXN = 5e2 + 10;
set < pair < int, int > > adj[MAXN];
int wrong[MAXN];
bool visited[MAXN];
int n, m;
set < int > edges;
vector < int > set_to_vector(set < int >& st)
{
vector < int > result;
for(int x : st)
{
result.push_back(x);
}
return result;
}
void dfs1(int u)
{
visited[u] = true;
for(pair < int, int > p : adj[u])
{
int v = p.first;
int idx = p.second;
if(visited[v])
continue;
edges.insert(idx);
dfs1(v);
}
}
bool lampa;
vector < int > cur_cycle;
vector < int > cycle;
void dfs_cycle(int u, int par, int to, int e)
{
if(e != -1)
{
cur_cycle.push_back(e);
}
if(u == to)
{
lampa = true;
cycle = cur_cycle;
return;
}
for(pair < int, int > p : adj[u])
{
int v = p.first;
int idx = p.second;
if(v == par)
continue;
dfs_cycle(v, u, to, idx);
}
if(e != -1)
{
cur_cycle.pop_back();
}
}
vector<int> find_roads(int N, vector<int> U, vector<int> V)
{
srand(time(nullptr));
n = N;
m = U.size();
for(int i = 0; i < m; i++)
{
wrong[i] = 0;
}
for(int i = 0; i < m; i++)
{
adj[U[i]].insert({V[i], i});
adj[V[i]].insert({U[i], i});
}
dfs1(1);
assert(edges.size() == n - 1);
for(int i = 0; i < n; i++)
{
adj[i].clear();
}
for(int idx : edges)
{
int u = U[idx];
int v = V[idx];
adj[u].insert({v, idx});
adj[v].insert({u, idx});
}
int best = count_common_roads(set_to_vector(edges));
while(best != n - 1)
{
set < int > old_edges = edges;
int found = rand() % m;
while(wrong[found] || old_edges.count(found))
{
found = rand() % m;
}
edges.insert(found);
int u = U[found];
int v = V[found];
cur_cycle.clear();
dfs_cycle(u, u, v, -1);
adj[u].insert({v, found});
adj[v].insert({u, found});
int del = rand() % (int)cycle.size();
int idx = cycle[del];
int udel = U[idx];
int vdel = V[idx];
edges.erase(idx);
adj[udel].erase({vdel, del});
adj[vdel].erase({udel, del});
int cur = count_common_roads(set_to_vector(edges));
if(cur > best)
{
best = cur;
for(int i = 0; i < m; i++)
{
wrong[i] = 0;
}
}
else if(cur <= best)
{
if(cur < best)
wrong[found] = true;
edges.insert(del);
adj[udel].insert({vdel, del});
adj[vdel].insert({udel, del});
edges.erase(found);
adj[u].erase({v, found});
adj[v].erase({u, found});
}
}
return set_to_vector(edges);
}
