#include "simurgh.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define query count_common_roads
const int maxN = 500;
struct Jmp
{
int to, ind;
operator int&() { return to; }
operator const int&() const { return to; }
};
int in[maxN], out[maxN];
Jmp par[maxN];
int gold[maxN * maxN];
vector<int> dfsq;
vector<Jmp> nei[maxN];
vector<int> same[maxN * maxN];
Jmp fup[maxN];
map<vector<int>, int> cache;
int Query(vector<int> q)
{
auto it = cache.find(q);
if (it != cache.end()) return it->second;
return cache[q] = query(q);
}
inline bool Upper(int u, int v) { return in[u] <= in[v] && out[u] >= out[v]; }
bool used[maxN];
void DFS(int v, Jmp p)
{
// cerr << "v: " << v << '\n';
static int time = 0;
used[v] = true;
in[v] = ++time;
par[v] = p;
fup[v] = {-1, -1};
for (Jmp to: nei[v])
if (!used[to])
{
dfsq.push_back(to.ind);
DFS(to, {v, to.ind});
if (p != -1)
if (fup[v] == -1 || (fup[to] != -1 && in[fup[to]] <= in[fup[v]]))
fup[v] = fup[to];
}
else if (to != p && p != -1)
if (fup[v] == -1 || in[to] <= in[fup[v]])
fup[v] = to;
out[v] = time;
}
void DFS1(int v)
{
for (int to: same[v])
if (gold[to] == -1)
{
gold[to] = gold[v];
DFS1(to);
}
}
int pr[maxN * maxN], sz[maxN * maxN], ok[maxN * maxN];
void MakeSet(int i) { pr[i] = i; sz[i] = 1; }
int Set(int i) { return pr[i] == i ? i : pr[i] = Set(pr[i]); }
void Union(int i, int j)
{
i = Set(i), j = Set(j);
if (i == j) return;
if (sz[i] > sz[j]) swap(i, j);
sz[j] += sz[i];
ok[j] = max(ok[j], ok[i]);
pr[i] = j;
}
vector<int> find_roads(int n, vector<int> us, vector<int> vs)
{
int m = us.size();
fill(gold, gold + m, -1);
for (int i = 0; i < m; ++i)
{
MakeSet(i);
nei[us[i]].push_back({vs[i], i});
nei[vs[i]].push_back({us[i], i});
}
DFS(0, {-1, -1});
// for (int i = 0; i < n; ++i)
// cerr << "fup[" << i << "] = " << fup[i].to << '\n';
int dfsans = Query(dfsq);
for (int i = 0; i < m; ++i)
if (in[us[i]] > in[vs[i]])
swap(us[i], vs[i]);
for (int i = 0; i < m; ++i)
{
int u = us[i], v = vs[i];
if (fup[v] == -1 || in[fup[v]] > in[u]) // Is a birdge.
{
gold[i] = 1;
continue;
}
if (par[v] == u) continue;
while (true)
{
int backe = i, dfse = par[v].ind;
if (Set(backe) == Set(dfse))
{}
else if (ok[Set(backe)] && ok[Set(dfse)])
{}
else
{
// cerr << dfse << ' ' << backe << '\n';
int j = find(dfsq.begin(), dfsq.end(), dfse) - dfsq.begin();
dfsq[j] = backe;
int curans = Query(dfsq);
if (curans == dfsans)
{
same[backe].push_back(dfse);
same[dfse].push_back(backe);
Union(dfse, backe);
}
else if (curans > dfsans)
{
gold[backe] = 1, gold[dfse] = 0;
ok[Set(backe)] = ok[Set(dfse)] = 1;
}
else
{
gold[backe] = 0, gold[dfse] = 1;
ok[Set(backe)] = ok[Set(dfse)] = 1;
}
dfsq[j] = dfse;
}
if ((v = par[v]) == u) break;
}
}
for (int i = 0; i < m; ++i)
if (gold[i] != -1)
DFS1(i);
vector<int> ans;
for (int i = 0; i < m; ++i)
if (gold[i] == 1)
ans.push_back(i);
return ans;
}
