#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define ve vector
#define ll long long
#define ii pair<int, int>
#define fi first
#define se second
int N;
set<int> ans;
struct DSU{
int par[500];
int si=0;
DSU(int siz){
si=siz;
reset();
}
void reset(){
for(int i=0; i<si; i++) par[i]=i;
}
int root(int x) {
return (x==par[x]) ? x : par[x]=root(par[x]);
}
void doUnion(int a, int b){
par[root(a)]=root(b);
}
};
int edgeInd[500][500];
DSU components(500);
int cutTime=0;
ve<bool> vis(500, false);
ve<int> firstTime(500, -1);
ve<int> lowTime(500, -1);
bool cutEdge[500][500];
void cutDFS(int cur, int par){
vis[cur]=true;
firstTime[cur] = lowTime[cur] = cutTime++;
for(int i=0; i<N; i++){
if(edgeInd[cur][i]==-1 || i==par) continue;
if(vis[i]) lowTime[cur] = min(lowTime[cur], firstTime[i]);
else{
cutDFS(i, cur);
lowTime[cur] = min(lowTime[cur], lowTime[i]);
if(lowTime[i] > firstTime[cur]) {
cutEdge[cur][i] = cutEdge[i][cur]=true;
}
}
}
}
ve<ii> cutEdges;
void findCutEdges(){
cutDFS(0, 0);
for(int i=0; i<N; i++){
for(int j=i+1; j<N; j++){
if(edgeInd[i][j]==-1) continue;
if(!cutEdge[i][j]){
components.doUnion(i, j);
}
else{
ans.insert(edgeInd[i][j]);
cutEdges.push_back({i, j});
}
}
}
}
ve<ii> baseTree;
bool treeVis[500];
void treeDFS(int x){
treeVis[x]=true;
for(int i=0; i<N; i++){
if(edgeInd[x][i]==-1) continue;
if(!treeVis[i]){
baseTree.push_back({x, i});
treeDFS(i);
}
}
}
ve<ve<int>> cycs;
bool earEdgeUsed[500][500];
bool inEar[500];
int earVis[500];
int curEarVis=0;
bool debug=false;
bool earDFS(int x, int par){
if(inEar[x]){
cycs.back().push_back(x);
return true;
}
if(earVis[x] == curEarVis) return false;
earVis[x] = curEarVis;
cycs.back().push_back(x);
for(int i=0; i<N; i++){
if(edgeInd[x][i]==-1 || cutEdge[x][i] || i==par) continue;
if(earDFS(i, x)) return true;
}
cycs.back().pop_back();
return false;
}
ve<ii> knownEdges;
void ear(int start){
ve<int> nodes = {start};
cycs.clear();
while(nodes.size()>0){
int cur=nodes.back();
int next=-1;
for(int i=0; i<N; i++){
if(edgeInd[cur][i]==-1 || cutEdge[cur][i] || earEdgeUsed[cur][i]) continue;
next=i;
break;
}
if(next==-1){
nodes.pop_back();
continue;
}
cycs.push_back({cur});
inEar[cur]=true;
curEarVis++;
earVis[cur]=curEarVis;
earDFS(next, cur);
for(int i=0; i<cycs.back().size()-1; i++){
int a=cycs.back()[i];
int b=cycs.back()[i+1];
inEar[a]=true;
if(!inEar[b]) nodes.push_back(b);
inEar[b]=true;
earEdgeUsed[a][b] = earEdgeUsed[b][a] = true;
}
}
ve<ve<int>> adj(N);
ve<int> vis(N, -1);
ve<int> par(N, -1);
ve<bool> foundNode(N,false);
for(int earInd=0; earInd<cycs.size(); earInd++){
int s = cycs[earInd][0], e=cycs[earInd].back();
bool skip=true;
for(int i=0; i<cycs[earInd].size(); i++){
if(!foundNode[cycs[earInd][i]]) skip=false;
foundNode[cycs[earInd][i]] = true;
}
if(skip) continue;
//bfs to get from e to s on adj of prev edges:
queue<ii> q;
q.push({e, e});
while(q.size()>0){
ii cur=q.front();
q.pop();
if(vis[cur.fi]==earInd) continue;
vis[cur.fi]=earInd;
par[cur.fi] = cur.se;
if(cur.fi==s) break;
for(int i:adj[cur.fi]) q.push({i, cur.fi});
}
ve<int> cyc;
int cur=s;
while(par[cur]!=cur){
cyc.push_back(par[cur]);
cur=par[cur];
}
reverse(cyc.begin(), cyc.end());
int cycRedundant = cyc.size();
for(int i=0; i<cycs[earInd].size(); i++){
cyc.push_back(cycs[earInd][i]);
}
if(false){
cout<<"Ear "<<earInd<<": ";
for(int i:cycs[earInd]) cout<<i<<" ";
cout<<endl;
}
if(false){
cout<<"Cycle (redundant: "<<cycRedundant<<"): ";
for(int i:cyc) cout<<i<<" ";
cout<<endl;
}
//Brute force on the cycle:
//set up tree:
ve<int> tree;
ve<int> treeInd(N);
DSU inTree(N);
int missing = cyc.size()-2;
for(int i=0; i<cyc.size()-1; i++){
int a=cyc[i], b=cyc[i+1];
inTree.doUnion(a, b);
tree.push_back(edgeInd[a][b]);
treeInd[i] = i;
if(i==missing){
treeInd[i] = -1;
tree.pop_back();
}
}
for(ii it:baseTree){
if(inTree.root(it.fi)!=inTree.root(it.se)){
tree.push_back(edgeInd[it.fi][it.se]);
inTree.doUnion(it.fi, it.se);
}
}
int ma=0;
ve<int> cou(cyc.size()-1, -1);
for(int i=0; i<cyc.size()-1; i++){
int a=cyc[i], b=cyc[i+1];
if(i!=missing){
int newa = cyc[missing], newb = cyc[missing+1];
tree[treeInd[i]] = edgeInd[newa][newb];
treeInd[missing] = treeInd[i];
treeInd[i] = -1;
missing = i;
}
cou[i] = count_common_roads(tree);
ma = max(ma, cou[i]);
}
for(int i=0; i<cyc.size()-1; i++){
int a=cyc[i], b=cyc[i+1];
if(i==cyc.size()-2) continue;//so get a tree
if(cou[i]<ma){
int ind = edgeInd[a][b];
if(ans.find(ind)==ans.end()) ans.insert(ind);
}
knownEdges.push_back({a, b});
}
for(int i=0; i<cycs[earInd].size()-1; i++){
int a=cycs[earInd][i], b=cycs[earInd][i+1];
adj[a].push_back(b);
adj[b].push_back(a);
}
}
}
ve<ii> knownTree;
int deg[500];
void calcDeg(int x){
DSU con(N);
ve<int> tree;
int sub = 0;
for(int i=0; i<N; i++){
if(edgeInd[x][i]==-1) continue;
tree.push_back(edgeInd[x][i]);
if(ans.find(edgeInd[x][i]) != ans.end()) sub++;
con.doUnion(x, i);
}
for(ii it:knownTree){
if(con.root(it.fi) == con.root(it.se)) continue;
tree.push_back(edgeInd[it.fi][it.se]);
if(ans.find(edgeInd[it.fi][it.se]) != ans.end()) sub++;
con.doUnion(it.fi, it.se);
}
deg[x] = count_common_roads(tree) - sub;
}
void solve(){
//with degree one verts, binary search for leaf edge and then remove vert.
stack<int> s;
for(int i=0; i<N; i++){
if(deg[i]==1) s.push(i);
}
while(ans.size()<N-1){
int x = s.top();
s.pop();
if(deg[x]==0) continue;
int l=0, r=N-1;
while(l<r){
int m=(l+r)/2;
DSU con(N);
ve<int> tree;
int sub = 0;
for(int i=l; i<=m; i++){
if(edgeInd[x][i]==-1) continue;
tree.push_back(edgeInd[x][i]);
if(ans.find(edgeInd[x][i]) != ans.end()) sub++;
con.doUnion(x, i);
}
for(ii it:knownTree){
if(con.root(it.fi) == con.root(it.se)) continue;
tree.push_back(edgeInd[it.fi][it.se]);
if(ans.find(edgeInd[it.fi][it.se]) != ans.end()) sub++;
con.doUnion(it.fi, it.se);
}
assert(tree.size()==N-1);
int count = count_common_roads(tree) - sub;
if(count >0) r=m;
else l=m+1;
}
ans.insert(edgeInd[l][x]);
deg[x]--;
deg[l]--;
if(deg[l]==1) s.push(l);
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
N = n;
if(n==2){
ve<int> res = {0};
return res;
}
for(int i=0; i<500; i++){
for(int j=0; j<500; j++){
edgeInd[i][j]=-1;
}
}
for(int i=0; i < u.size(); i++){
edgeInd[u[i]][v[i]] = i;
edgeInd[v[i]][u[i]] = i;
}
findCutEdges();
treeDFS(0);
set<int> foundComp;
for(int i=0; i<N; i++){
if(foundComp.find(components.root(i))==foundComp.end()){
foundComp.insert(components.root(i));
ear(i);
}
}
//now know state of all edges in knownEdges and cutEdges, which together form a tree.
for(ii it:knownEdges) knownTree.push_back(it);
for(ii it:cutEdges) knownTree.push_back(it);
for(int i=0; i<N; i++) calcDeg(i);
solve();
ve<int> res;
for(int i:ans) res.push_back(i);
return res;
}
