#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 250;
const int MAXM = 30010;
int n, m;
int depth[MAXN];
int isRoyal[MAXM];
int ancNode[MAXN], ancEdge[MAXN];
bool mark[MAXN];
bool DFSTree[MAXM];
vector<int> tree;
vector<int> adj[MAXN];
vector<int> indEdge[MAXN];
void DFS(int cur)
{
mark[cur] = true;
for(int i = 0 ; i < (int)adj[cur].size() ; i++)
{
int viz = adj[cur][i];
int ind = indEdge[cur][i];
if( mark[viz] ) continue;
DFSTree[ind] = true;
tree.push_back( ind );
ancNode[viz] = cur;
ancEdge[viz] = ind;
depth[viz] = depth[cur] + 1;
DFS( viz );
}
}
int query(int newEdge = -1, int blockEdge = -1)
{
vector<int> q;
if( newEdge != -1 ) q.push_back( newEdge );
for(int i = 0 ; i < (int)tree.size() ; i++)
if( tree[i] != blockEdge ) q.push_back( tree[i] );
return count_common_roads( q );
}
vector<int> find_roads(int N, vector<int> u, vector<int> v)
{
n = N; m = (int)u.size();
for(int i = 0 ; i < m ; i++)
{
adj[ u[i] ].push_back( v[i] );
adj[ v[i] ].push_back( u[i] );
indEdge[ u[i] ].push_back( i );
indEdge[ v[i] ].push_back( i );
isRoyal[i] = -1;
}
DFS( 1 );
int qtdRoyalTree = query();
for(int i = 0 ; i < m ; i++)
{
if( DFSTree[i] ) continue;
if( depth[ u[i] ] > depth[ v[i] ] )
swap( u[i] , v[i] );
int cur = v[i];
int known = -1;
vector<int> unknown;
while( cur != u[i] )
{
if( isRoyal[ ancEdge[cur] ] != -1 ) known = ancEdge[cur];
else unknown.push_back( ancEdge[cur] );
cur = ancNode[cur];
}
if( known != -1 )
{
int newQtd = query( i , known );
if( newQtd == qtdRoyalTree ) isRoyal[i] = isRoyal[known];
else isRoyal[i] = 1 - isRoyal[known];
for(int j = 0 ; j < (int)unknown.size() ; j++)
{
newQtd = query( i , unknown[j] );
if( newQtd == qtdRoyalTree ) isRoyal[ unknown[j] ] = isRoyal[i];
else isRoyal[ unknown[j] ] = 1 - isRoyal[i];
}
continue;
}
for(int j = 0 ; j < (int)unknown.size() ; j++)
{
int newQtd = query( i , unknown[j] );
if( isRoyal[i] != -1 )
{
if( newQtd == qtdRoyalTree ) isRoyal[ unknown[j] ] = isRoyal[i];
else isRoyal[ unknown[j] ] = 1 - isRoyal[i];
continue;
}
if( newQtd != qtdRoyalTree )
{
if( newQtd > qtdRoyalTree ) isRoyal[i] = 1;
else isRoyal[i] = 0;
isRoyal[ unknown[j] ] = 1 - isRoyal[i];
for(int k = 0 ; k < j ; k++)
isRoyal[ unknown[k] ] = isRoyal[i];
}
}
if( isRoyal[i] == -1 )
{
isRoyal[i] = 0;
for(int j = 0 ; j < (int)unknown.size() ; j++)
isRoyal[ unknown[j] ] = 0;
}
}
for(int i = 0 ; i < m ; i++)
if( isRoyal[i] == -1 ) isRoyal[i] = 1;
vector<int> ans;
for(int i = 0 ; i < m ; i++)
if( isRoyal[i] == 1 ) ans.push_back( i );
return ans;
}
