#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define SZ(x) int((x).size())
#define X first
#define Y second
#define sep ' '
const ll MAXN = 510; //TODO: fix MAXN
int n , m , common , mark[MAXN] , H[MAXN] , par[MAXN] , ind[MAXN] , tree[MAXN * MAXN] , ans[MAXN * MAXN];
vector<pii> E , adj[MAXN] , back_edge[MAXN];
int query(int A[]){
vector<int> vec;
for(int i = 0 ; i < m ; i++){
if(A[i]){
vec.push_back(i);
}
}
//assert(SZ(vec) == n - 1);
return count_common_roads(vec);
}
int query_back_edge(vector<pii> &v , int l , int r){
assert(l > 0);
int sum = common;
for(int i = l ; i < r ; i++){
tree[v[i].Y] = 1;
tree[ind[v[i - 1].X]] = 0;
sum -= ans[ind[v[i - 1].X]];
}
int res = query(tree);
for(int i = l ; i < r ; i++){
tree[v[i].Y] = 0;
tree[ind[v[i - 1].X]] = 1;
}
return res - sum;
}
void DFS(int v){
mark[v] = 1;
for(pii i : adj[v]){
int u = i.X , w = i.Y;
if(mark[u]){
continue;
}
//cout << v << sep << u << sep << w << endl;
par[u] = v;
ind[u] = w;
tree[w] = 1;
H[u] = H[v] + 1;
DFS(u);
}
}
void Calc(int v , int u , int index){
int mx = common , W = -1 , x = v , flag = 1;
while(x != u){
if(ans[ind[x]] == -1){
flag = 0;
}
x = par[x];
}
if(flag){
return;
}
vector<pii> res;
tree[index] = 1;
x = v;
while(x != u){
if(ans[ind[x]] != -1){
if(W != -1){
res.push_back({W - ans[ind[x]] , x});
x = par[x];
continue;
}
tree[ind[x]] = 0;
int cur = query(tree);
tree[ind[x]] = 1;
res.push_back({cur , x});
W = cur + ans[ind[x]];
x = par[x];
continue;
}
tree[ind[x]] = 0;
int cur = query(tree);
tree[ind[x]] = 1;
res.push_back({cur , x});
x = par[x];
}
tree[index] = 0;
//cout << "==========" << endl;
//cout << v << sep << u << sep << index << endl;
for(pii i : res){
//cout << i.X << sep << i.Y << endl;
mx = max(mx , i.X);
}
for(pii i : res){
if(i.X == mx){
ans[ind[i.Y]] = 0;
}
else{
ans[ind[i.Y]] = 1;
}
}
if(common == mx){
ans[index] = 0;
}
else{
ans[index] = 1;
}
}
void solve(int v , int l , int r , int cnt){
if(cnt == 0){
return;
}
if(r - l == 1){
ans[back_edge[v][l].Y] = 1;
return;
}
int mid = l + r >> 1;
int L = query_back_edge(back_edge[v] , l , mid) , R = cnt - L;
solve(v , l , mid , L);
solve(v , mid , r , R);
}
int cmp(pii x , pii y){
return H[x.X] > H[y.X];
}
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
fill(ans , ans + MAXN * MAXN, -1);
n = N; m = SZ(U);
for(int i = 0 ; i < m ; i++){
adj[V[i]].push_back({U[i] , i});
adj[U[i]].push_back({V[i] , i});
E.push_back({V[i] , U[i]});
}
DFS(0);
common = query(tree);
for(int i = 0 ; i < m ; i++){
if(H[E[i].X] < H[E[i].Y]){
swap(E[i].X , E[i].Y);
}
}
for(int i = 0 ; i < m ; i++){
if(tree[i] == 0){
Calc(E[i].X , E[i].Y , i);
}
}
for(int i = 0 ; i < n ; i++){
back_edge[i].push_back({i , 0});
}
for(int i = 0 ; i < m ; i++){
if(tree[i] == 1 && ans[i] == -1){
ans[i] = 1;
}
if(ans[i] == -1){
back_edge[E[i].X].push_back({E[i].Y , i});
}
}
for(int i = 0 ; i < n ; i++){
sort(back_edge[i].begin() , back_edge[i].end() , cmp);
int cnt = query_back_edge(back_edge[i] , 1 , SZ(back_edge[i]));
solve(i , 1 , SZ(back_edge[i]) , cnt);
}
vector<int> res;
for(int i = 0 ; i < m ; i++){
if(ans[i] == -1){
ans[i] = 0;
}
if(ans[i]){
res.push_back(i);
}
}
return res;
}
