#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
int N, M, id[509][509], x[130009], y[130009], ans[130009], q[130009];
bool traversed[130009];
bool anyEdge[509][509];
vector < int > v[509];
namespace edgesFinder
{
bool ap[509];
vector < int > starterPack, currComp;
void dfs (int nod)
{
ap[nod] = 1, currComp.push_back (nod);
for (auto it : v[nod])
if (ap[it] == 0)
starterPack.push_back (id[nod][it]), dfs (it);
}
void findEdges (int nod)
{
memset (ap, 0, sizeof (ap)), ap[nod] = 1;
starterPack.clear ();
vector < vector < int > > currEdges;
vector < int > representative;
for (int i=0; i<N; i++)
if (ap[i] == 0)
{
currComp.clear ();
dfs (i);
vector < int > curr;
for (auto j : currComp)
if (anyEdge[nod][j])
curr.push_back (id[nod][j]);
currEdges.push_back (curr);
representative.push_back (curr[0]);
}
for (int i=0; i<currEdges.size (); i++)
if (currEdges[i].size () == 1)
traversed[representative[i]] = 1, ans[representative[i]] = 1;
else
{
vector < int > curr = starterPack;
for (int j=0; j<currEdges.size (); j++)
if (j != i)
curr.push_back (representative[j]);
int maxi = -1;
bool anyOther = 0;
for (auto j : currEdges[i])
if (!traversed[j])
{
curr.push_back (j);
q[j] = count_common_roads (curr);
if (q[j] > maxi)
maxi = q[j];
curr.pop_back ();
}
else
if (traversed[j] == 1 && ans[j] == 1 && !anyOther)
{
anyOther = 1;
curr.push_back (j);
int currQ = count_common_roads (curr);
if (currQ > maxi)
maxi = currQ;
curr.pop_back ();
}
for (auto j : currEdges[i])
if (!traversed[j])
{
traversed[j] = 1;
ans[j] = (maxi == q[j]);
}
}
}
}
vector < int > h[509];
void findFixedSTcompleteGraph ()
{
vector < int > curr;
for (int i=1; i<N - 1; i++)
curr.push_back (id[i][i + 1]);
int maxi = -1;
for (int i=1; i<N; i++)
{
curr.push_back (id[0][i]);
q[i] = count_common_roads (curr);
if (q[i] > maxi)
maxi = q[i];
curr.pop_back ();
}
for (int i=1; i<N; i++)
traversed[id[0][i]] = 1,
ans[id[0][i]] = (q[i] == maxi),
h[0].push_back (i),
h[i].push_back (0);
}
namespace edgesFinderGivenFixedST
{
bool ap[509];
void dfs (int nod, int &currCost, vector < int > &curr)
{
ap[nod] = 1;
for (auto it : h[nod])
if (ap[it] == 0)
curr.push_back (id[nod][it]),
currCost += ans[id[nod][it]],
dfs (it, currCost, curr);
}
void findEdges (int nod)
{
vector < int > possibleEdges;
for (int i=0; i<N; i++)
if (anyEdge[nod][i] && !traversed[id[nod][i]])
possibleEdges.push_back (id[nod][i]),
traversed[id[nod][i]] = 1;
for (int l=0; l<possibleEdges.size (); l++)
{
int p = l, u = possibleEdges.size () - 1, ras = possibleEdges.size ();
while (p <= u)
{
int mij = (p + u) >> 1, q = 0;
vector < int > curr;
memset (ap, 0, sizeof (ap)), ap[nod] = 1;
for (int i=l; i<=mij; i++)
{
int otherEnd = x[possibleEdges[i]] ^ y[possibleEdges[i]] ^ nod;
ap[otherEnd] = 1, curr.push_back (possibleEdges[i]);
}
dfs (nod, q, curr);
for (int i=l; i<=mij; i++)
{
int otherEnd = x[possibleEdges[i]] ^ y[possibleEdges[i]] ^ nod;
dfs (otherEnd, q, curr);
}
if (count_common_roads (curr) > q) ras = mij, u = mij - 1;
else p = mij + 1;
}
if (ras == possibleEdges.size ()) break;
ans[possibleEdges[ras]] = 1, l = ras;
}
}
}
vector < int > find_roads (int nn, vector < int > uu, vector < int > vv)
{
N = nn, M = uu.size ();
for (int i=0; i<M; i++)
anyEdge[uu[i]][vv[i]] = anyEdge[vv[i]][uu[i]] = 1,
id[uu[i]][vv[i]] = id[vv[i]][uu[i]] = i,
x[i] = uu[i], y[i] = vv[i],
v[x[i]].push_back (y[i]),
v[y[i]].push_back (x[i]);
if (N <= 240)
{
for (int i=0; i<N; i++)
edgesFinder::findEdges (i);
}
else
{
//bool isNew[100009];
//memset (isNew, 0, sizeof (isNew));
findFixedSTcompleteGraph ();
for (int i=0; i<N; i++)
{
edgesFinderGivenFixedST::findEdges (i);
/*printf ("added %d's edges\n", i);
for (int j=0; j<M; j++)
if (traversed[j] == 1 && isNew[j] == 0)
{
printf ("%d -> %d\n", j, ans[j]);
isNew[j] = 1;
}*/
}
}
vector < int > finalAns;
for (int i=0; i<M; i++)
if (ans[i])
finalAns.push_back (i);
return finalAns;
}
