//#include "simurgh.h"
#include <bits/stdc++.h>
//#include "simurgh.h"
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define f first
#define s second
#define pb push_back
#define mx 250003
#define ALL(x) x.begin(),x.end()
using namespace std;
int di[mx],M,idx,brp[505][505],level[mx];
bool sudah[mx];
int P[mx];
vector<pair<int,int>>cycle;
vector<int> r;
vector<int>g[mx];
#include <cstdio>
#include <cassert>
#include <vector>
#include <cstdlib>
#include <string>
using namespace std;
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);
}
void dfs(int now,int par=0,int lev=1){
sudah[now]=true;
level[now]=lev;
for(auto i:g[now]){
if(i==par)
continue;
if(!sudah[i]){
P[i]=now;
di[brp[now][i]]=idx++;
r.pb(brp[now][i]);
dfs(i,now,lev+1);
}
else if(level[i]<level[now]){
cycle.pb({now,i});
}
}
}
bool cmp(pair<int,int>x,pair<int,int>y){
return level[x.s]>level[y.s];
}
vector<int> find_roads(int N, vector<int> u, vector<int> v) {
M=u.size();
for(int i=0;i<M;i++){
g[u[i]+1].pb(v[i]+1);
g[v[i]+1].pb(u[i]+1);
brp[u[i]+1][v[i]+1]=i;
brp[v[i]+1][u[i]+1]=i;
}
memset(di,-1,sizeof di);
dfs(1,0);
vector<int>satu(N-1);
int maks=count_common_roads(r);
// for(int i:r)cout<<i<<" ";
// cout<<endl;
// cout<<maks<<endl;
sort(ALL(cycle),cmp);
// debug(maks);
for(auto i:cycle){
// cout<<i.f<<" -> "<<i.s<<endl;
int dari=i.f,ke=i.s;
int besar=0;
while(dari!=ke){
// if(dari)cout<<"ini "<<brp[dari][P[dari]]<<" "<<dari<<" "<<P[dari]<<endl;
if(di[brp[dari][P[dari]]]!=-1){
int tmp=brp[dari][P[dari]];
r[di[tmp]]=brp[i.f][i.s];
int sem=count_common_roads(r);
// debug(sem);
if(sem>besar){
satu=r;
besar=sem;
}
r[di[tmp]]=brp[dari][P[dari]];
}
dari=P[dari];
}
if(besar>maks){
maks=besar;
r=satu;
memset(di,-1,sizeof di);
for(int i=0;i<N-1;i++){
di[r[i]]=i;
}
}
// for(int i:r)cout<<i<<' ';
// cout<<endl;
// debug(maks);
}
// cout<<maks<<endl;
return r;
}
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;
}
Compilation message
/tmp/ccjJ6KvX.o: In function `count_common_roads(std::vector<int, std::allocator<int> > const&)':
grader.cpp:(.text+0x2e0): multiple definition of `count_common_roads(std::vector<int, std::allocator<int> > const&)'
/tmp/ccr11MG0.o:simurgh.cpp:(.text+0x100): first defined here
/tmp/ccjJ6KvX.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccr11MG0.o:simurgh.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
