#include <bits/stdc++.h>
#include "simurgh.h"
#define all(x) (x).begin(),(x).end()
using namespace std;
//#define ask count_common_roads
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 500;
vector<pii> g[nmax];
vector<int> occ;
vector<int> candr;
int flag;
int cnt = 0;
int ask(vector<int> r) {
return count_common_roads(r);
}
void dfs(int x) {
occ[x] = flag;
for(auto [y, ptr] : g[x]) {
if(occ[y] != 0) continue;
//cerr << x << ' ' << y << '\t' << ptr << '\n';
occ[y] = flag;
candr.emplace_back(ptr);
dfs(y);
}
return;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
occ.resize(n);
vector<int> isgood(sz(u), 0);
vector<int> checked(sz(u), 0);
for(int i = 0; i < sz(u); i++) {
g[u[i]].emplace_back(v[i], i);
g[v[i]].emplace_back(u[i], i);
}
for(int i = 0; i < n; i++) {
fill(all(occ), 0);
candr.clear();
occ[i] = -1;
vector<vector<int>> atrs;
atrs.emplace_back();
vector<int> nv;
flag = 0;
for(auto [x, ptr] : g[i]) {
if(occ[x] == 0) {
flag++;
dfs(x);
nv.emplace_back(ptr);
atrs.emplace_back();
atrs.back().emplace_back(ptr);
}
else
atrs[occ[x]].emplace_back(ptr);
}
//cerr << i <<'\n';
//for(auto x : candr) cerr << x << ' ';
//cerr << '\n';
//for(auto x : nv) cerr << x << ' ';
//cerr << '\n';
int startmn = sz(candr) - 1;
copy(all(nv), back_inserter(candr));
for(int i = 1; i <= flag; i++) {
//cerr << "--\n";
vector<int> rez;
int mx = -1;
for(int j = 0; j < sz(atrs[i]); j++) {
int u = atrs[i][j];
candr[startmn + i] = u;
if(checked[u] && isgood[u]) { mx = ask(candr); break; }
}
for(int j = 0; j < sz(atrs[i]); j++) {
int u = atrs[i][j];
candr[startmn + i] = u;
if(!checked[u])
rez.emplace_back(ask(candr));
else
rez.emplace_back(-1);
}
if(mx == -1)
mx = *max_element(all(rez));
for(int j = 0; j < sz(atrs[i]); j++) {
checked[atrs[i][j]] = 1;
if(rez[j] == mx)
isgood[atrs[i][j]] = 1;
}
//cerr << "--\n";
}
//cerr << "=======\n";
}
vector<int> lst;
for(int i = 0; i < sz(isgood); i++)
if(isgood[i])
lst.emplace_back(i);
//for(auto x : lst)
//cerr << x << ' ';
//cerr << '\n';
return lst;
}
/**
Anul asta se da centroid.
-- Surse oficiale
*/
