#include<bits/stdc++.h>
#include "simurgh.h"
using namespace std;
#define ll long long
// static int MAXQ = 30000;
// static int n, m, q = 0;
// static vector<int> u, v;
// static vector<bool> goal;
// static void wrong_answer() {
// printf("NO\n");
// exit(0);
// }
// static bool is_valid(const vector<int>& r) {
// if(int(r.size()) != n - 1)
// return false;
// for(int i = 0; i < n - 1; i++)
// if (r[i] < 0 || r[i] >= m)
// return false;
// return true;
// }
// static int _count_common_roads_internal(const vector<int>& r) {
// if(!is_valid(r)){
// wrong_answer();
// }
// int common = 0;
// for(int i = 0; i < n - 1; i++) {
// bool is_common = goal[r[i]];
// if (is_common)
// common++;
// }
// return common;
// }
// int count_common_roads(const vector<int>& r) {
// q++;
// if(q > MAXQ)
// wrong_answer();
// return _count_common_roads_internal(r);
// }
vector<ll>adj[505];
struct Edge{
ll u,v,id;
};
// int count_common_roads(int[] r)
struct DSU{
vector<ll>fa,siz;
void init(ll n){
fa.resize(n+5); siz.resize(n+5);
for(int i=0;i<n+5;i++){
fa[i]=i,siz[i]=1;
}
}
ll root(ll x){
if(fa[x]==x)return x;
return fa[x]=root(fa[x]);
}
void unite(ll u, ll v){
u=root(u); v=root(v);
if(siz[u]<siz[v])swap(u,v);
fa[v]=u; siz[u]+=siz[v];
}
};
int Query(vector<int>r){
return count_common_roads(r);
}
enum Type {Normal, Royal, Undefined};
struct Graph{
vector<Edge>edge,tedge;
vector<vector<pair<ll,ll> > >adj,tadj;
vector<vector<ll> >res;
vector<ll>dep,fa,highest,eid;
vector<bool>vis;
vector<Type>type;
vector<ll>tree; int tree_val;
void init(ll n){
adj.resize(n+5); tadj.resize(n+5); vis.resize(n+5); dep.resize(n+5); fa.resize(n+5); type.resize(n*n+5); highest.resize(n+5); eid.resize(n+5); res.resize(n+5);
for(int i=0;i<n+5;i++){
res[i].resize(n+5);
}
for(int i=0;i<n+5;i++){
highest[i]=-1; eid[i]=-1;
}
for(int i=0;i<n*n+5;i++){
type[i]=Type::Undefined;
}
}
void add_edge(ll u, ll v, ll id){
edge.push_back({u,v,id}); adj[u].push_back({v,id}); adj[v].push_back({u,id});
res[u][v]=res[v][u]=id;
}
void dfs(ll s){
vis[s]=1;
for(auto& [u,id]: adj[s]){
if(!vis[u]){
dep[u]=dep[s]+1;
dfs(u); tadj[s].push_back({u,id}); tadj[u].push_back({s,id});
fa[u]=s; tedge.push_back({s,u,id});
tree.push_back(id);
}
}
}
void construct(ll s){
vis[s]=1;
highest[s]=dep[s]; eid[s]=-1;
for(auto& [u,id]: adj[s]){
if(!vis[u]){
construct(u);
if(highest[u]<highest[s]){
highest[s]=highest[u]; eid[s]=eid[u];
}
}
else{
if(u==fa[s])continue;
if(dep[u]<highest[s]){
highest[s]=dep[u]; eid[s]=id;
}
}
}
}
void clear(ll n){
for(int i=0;i<=n;i++)vis[i]=0;
}
void build_induced_subtree(ll n){
dep[0]=1;
dfs(0); clear(n);
construct(0); clear(n);
// for(int i=0;i<tree.size();i++){
// cout<<tree[i]<<" ";
// }
// cout<<'\n';
}
vector<ll>edge_list;
int pull(ll x, int add){
vector<int>qrylist;
if(x==-1){
for(auto& u: tree){
qrylist.push_back(u);
}
return Query(qrylist);
}
else{
qrylist.push_back(add);
for(auto& u: tree){
if(u!=x){
qrylist.push_back(u);
}
}
return Query(qrylist);
}
}
void build(ll u, ll v){
while(dep[u]!=dep[v]){
edge_list.push_back(res[u][fa[u]]); u=fa[u];
}
}
void process(ll edge_id){
vector<pair<ll,ll> >alls;
ll cnt=0;
ll wrt;
for(auto& u: edge_list){
if(type[u]!=Type::Undefined){
cnt++;
if(cnt==1){
wrt=pull(u,edge_id);
if(type[u]==Type::Royal){
if(tree_val==wrt)type[edge_id]=Type::Royal;
else type[edge_id]=Type::Normal;
}
else{
if(tree_val==wrt)type[edge_id]=Type::Normal;
else type[edge_id]=Type::Royal;
}
}
continue;
}
alls.push_back({pull(u,edge_id),u});
}
sort(alls.begin(),alls.end());
// add 1, neutral, minus 1
if(type[edge_id]==Type::Undefined){
if(alls[0].first==alls[alls.size()-1].first){
for(int i=0;i<alls.size();i++){
type[alls[i].second]=Type::Normal;
}
type[edge_id]=Type::Normal;
}
else{
ll mini=alls[0].first; ll maxi=alls[alls.size()-1].first;
if(mini<tree_val){
type[edge_id]=Type::Normal;
for(int i=0;i<alls.size();i++){
if(alls[i].first<tree_val)type[alls[i].second]=Type::Royal;
else type[alls[i].second]=Type::Normal;
}
}
else{
type[edge_id]=Type::Royal;
for(int i=0;i<alls.size();i++){
if(alls[i].first==tree_val)type[alls[i].second]=Type::Royal;
else type[alls[i].second]=Type::Normal;
}
}
}
}
else{
for(int i=0;i<alls.size();i++){
if(alls[i].first==tree_val){
type[alls[i].second]=type[edge_id];
}
else{
if(type[edge_id]==Type::Royal)type[alls[i].second]=Type::Normal;
else type[alls[i].second]=Type::Royal;
}
}
}
edge_list.clear();
}
void find_tree_edge(ll n){
tree_val=pull(-1,-1);
for(int i=1;i<n;i++){
ll req=res[i][fa[i]];
if(type[req]!=Type::Undefined)continue;
if(highest[i]!=dep[i]){
auto [u,v,id]=edge[eid[i]];
// cout<<"Debug : "<<i<<" "<<u<<" "<<v<<" "<<eid[i]<<'\n';
if(dep[u]<dep[v]){
swap(u,v);
}
build(u,v); process(id);
}
else{
ll req=res[i][fa[i]];
type[req]=Type::Royal;
}
}
}
ll qry(ll n, vector<Edge>& lst, ll l, ll r){
DSU d; d.init(n);
ll royals=0; // tedge
vector<int>used;
for(int i=l;i<=r;i++){
auto& [u,v,id]=lst[i];
d.unite(u,v); used.push_back(id);
}
for(auto& [u,v,id]: tedge){
if(d.root(u)!=d.root(v)){
used.push_back(id);
d.unite(u,v); royals+=(type[id]==Type::Royal);
}
}
return Query(used)-royals;
}
void dc(ll n, ll l, ll r, ll rem, vector<Edge>& lst){
if(l==r){
type[lst[l].id]=Type::Royal; return;
}
ll mid=(l+r)>>1;
ll lrem=qry(n,lst,l,mid); ll rrem=rem-lrem;
if(lrem!=0){
dc(n,l,mid,lrem,lst);
}
if(rrem!=0){
dc(n,mid+1,r,rrem,lst);
}
}
void deal(vector<Edge>lst, ll n){
DSU d;
d.init(n);
ll royals=0; // tedge
vector<int>used;
for(auto& [u,v,id]: lst){
d.unite(u,v); used.push_back(id);
}
for(auto& [u,v,id]: tedge){
if(d.root(u)!=d.root(v)){
used.push_back(id);
d.unite(u,v); royals+=(type[id]==Type::Royal);
}
}
ll val=Query(used);
if(val==royals){
for(int i=0;i<(int)lst.size();i++){
type[lst[i].id]=Type::Normal;
}
return;
}
else{
dc(n,0,(int)lst.size()-1,val-royals,lst);
for(int i=0;i<(int)lst.size();i++){
if(type[lst[i].id]==Type::Undefined){
type[lst[i].id]=Type::Normal;
}
}
return;
}
}
void remaining(ll n){
DSU dd[n+5]; vector<Edge>lst[n+5];
for(int i=1;i<=n;i++)dd[i].init(n);
for(auto& [u,v,id]: edge){
if(type[id]==Type::Undefined){
ll l=1,r=n;
while(l<r){
ll mid=(l+r)>>1;
if(dd[mid].root(u)!=dd[mid].root(v))r=mid;
else l=mid+1;
}
lst[l].push_back({u,v,id}); dd[l].unite(u,v);
}
}
for(int i=1;i<=n;i++){
if(lst[i].size()){
deal(lst[i],n);
}
}
}
};
vector<int>find_roads(int n, vector<int>u, vector<int>v){
int m=u.size();
for(int i=0;i<m;i++){
adj[u[i]].push_back(v[i]); adj[v[i]].push_back(u[i]);
}
Graph g;
g.init(n);
for(int i=0;i<m;i++){
g.add_edge(u[i],v[i],i);
}
g.build_induced_subtree(n);
// cout<<"Check\n";
g.find_tree_edge(n);
// cout<<"Check\n";
// for(int i=0;i<(int)u.size();i++){
// cout<<g.type[i]<<'\n';
// }
// cout<<'\n';
g.remaining(n);
vector<int>ans;
for(int i=0;i<(int)u.size();i++){
if(g.type[i]==Type::Royal){
// cout<<g.type[i]<<'\n';
ans.push_back(i);
}
}
// cout<<ans.size()<<"\n";
// for(auto& u: ans){
// cout<<u<<"\n";
// }
return ans;
}
// int main() {
// assert(2 == scanf("%d %d", &n, &m));
// u.resize(m);
// v.resize(m);
// for(int i = 0; i < m; i++)
// assert(2 == scanf("%d %d", &u[i], &v[i]));
// goal.resize(m, false);
// for(int i = 0; i < n - 1; i++) {
// int id;
// assert(1 == scanf("%d", &id));
// goal[id] = true;
// }
// vector<int> res = find_roads(n, u, v);
// if(_count_common_roads_internal(res) != n - 1)
// wrong_answer();
// printf("YES\n");
// return 0;
// }
