#include "simurgh.h"
#include <vector>
#include <stdio.h>
int Pa[505];
typedef struct edge edge;
struct edge
{
int v, i;
};
std::vector<edge> AdjList[505];
int isRoyal[200005];
int inMST[200005];
int PaI[505];
int H[505];
int UF(int u)
{
return (Pa[u] == -1)?u:(Pa[u] = UF(Pa[u]));
}
void dfs(int u, int pa)
{
H[u] = H[pa] + 1;
int i, v, s = AdjList[u].size();
for (i = 0; i < s; i++)
{
v = AdjList[u][i].v;
if (v != pa)
{
dfs(v, u);
PaI[v] = AdjList[u][i].i;
Pa[v] = u;
}
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
//random mst
int i;
int m = u.size();
for (i = 0; i < n; i++)
Pa[i] = -1;
int pu, pv;
std::vector<int> Ask;
for (i = 0; i < m; i++)
{
if ((pu = UF(u[i])) != (pv = UF(v[i])))
{
Pa[pu] = pv;
Ask.push_back(i);
inMST[i] = 1;
AdjList[u[i]].push_back({v[i], i});
AdjList[v[i]].push_back({u[i], i});
}
}
dfs(0, 0);
int K = count_common_roads(Ask), k;
// for (i = 0; i < n; i++)
// printf("pa%d = %d (%d) H%d\n", i, Pa[i], PaI[i], H[i]);
// printf("K%d\n", K);
int uu, vv;
int j;
std::vector<int> V;
std::vector<int> Vk;
for (i = 0; i < m; i++)
isRoyal[i] = -1;
for (i = 0; i < m; i++)
{
if (!inMST[i])
{
V.clear();
uu = u[i];
vv = v[i];
if (H[vv] > H[uu])
{
uu = v[i];
vv = u[i];
}
while (H[uu] > H[vv])
{
if (isRoyal[i] == -1 && isRoyal[PaI[uu]] >= 0)
{
// printf("PaI[uu] %d\n", PaI[uu]);
for (j = 0; j < Ask.size(); j++)
if (Ask[j] == PaI[uu])
Ask[j] = i;
k = count_common_roads(Ask);
// printf("k%d\n", k);
isRoyal[i] = k - K + isRoyal[PaI[uu]];
for (j = 0; j < Ask.size(); j++)
if (Ask[j] == i)
Ask[j] = PaI[uu];
}
V.push_back(PaI[uu]);
uu = Pa[uu];
}
if (H[uu] == H[vv])
{
while (uu != vv)
{
if (isRoyal[i] == -1 && isRoyal[PaI[uu]] >= 0)
{
// printf("PaI[uu] %d\n", PaI[uu]);
for (j = 0; j < Ask.size(); j++)
if (Ask[j] == PaI[uu])
Ask[j] = i;
k = count_common_roads(Ask);
// printf("k%d\n", k);
isRoyal[i] = k - K + isRoyal[PaI[uu]];
for (j = 0; j < Ask.size(); j++)
if (Ask[j] == i)
Ask[j] = PaI[uu];
}
else if (isRoyal[i] == -1 && isRoyal[PaI[vv]] >= 0)
{
// printf("PaI[vv] %d\n", PaI[vv]);
for (j = 0; j < Ask.size(); j++)
if (Ask[j] == PaI[vv])
Ask[j] = i;
k = count_common_roads(Ask);
// printf("k%d\n", k);
isRoyal[i] = k - K + isRoyal[PaI[vv]];
for (j = 0; j < Ask.size(); j++)
if (Ask[j] == i)
Ask[j] = PaI[vv];
}
V.push_back(PaI[uu]);
V.push_back(PaI[vv]);
uu = Pa[uu];
vv = Pa[vv];
}
if (uu == vv)
{
// printf("zero knowledge\n");
Vk.clear();
for (k = 0; k < V.size(); k++)
{
for (j = 0; j < Ask.size(); j++)
if (Ask[j] == V[k])
Ask[j] = i;
if (isRoyal[V[k]] == -1 || isRoyal[i] == -1)
Vk.push_back(count_common_roads(Ask));
else
Vk.push_back(K - isRoyal[V[k]] + isRoyal[i]);
// printf("Vk %d\n", Vk[Vk.size() - 1]);
for (j = 0; j < Ask.size(); j++)
{
// printf("ask %d\n", Ask[j]);
if (Ask[j] == i)
Ask[j] = V[k];
}
}
k = K;
for (j = 0; j < V.size(); j++)
if (Vk[j] > k)
k = Vk[j];
// printf("k%d\n", k);
isRoyal[i] = k - K;
for (j = 0; j < V.size(); j++)
isRoyal[V[j]] = K - Vk[j] + isRoyal[i];
}
}
}
}
std::vector<int> Ans;
for (i = 0; i < m; i++)
{
// printf("isRoyal %d\n", isRoyal[i]);
if (isRoyal[i])
Ans.push_back(i);
}
return Ans;
}
