#ifndef hwe
#include "simurgh.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#define POPCOUNT(n) (__builtin_popcountll((n)))
#define CLZ(n) (__builtin_clzll((n)))
#define CTZ(n) (__builtin_ctzll((n)))
#define LOG(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))
#define Int __int128
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;
template <class T1, class T2> bool maximize(T1 &x, T2 y) {
if (x < y) {
x = y;
return true;
}
return false;
}
template <class T1, class T2> bool minimize(T1 &x, T2 y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <class T> void remove_duplicate(vector<T> &ve) {
sort (ve.begin(), ve.end());
ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long random(long long l, long long r) {
return uniform_int_distribution<long long>(l, r)(rng);
}
template <class T> T random(T r) {
return rng() % r;
}
#ifdef hwe
int MAXQ = 30000;
int n, m, q = 0;
vector<int> u, v;
vector<bool> goal;
void wrong_answer() {
cout << "NO\n";
exit(0);
}
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;
// Check tree
return true;
}
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);
}
#endif
struct DSU {
vector<int> lab;
DSU(int n = 0) {
resize(n);
}
void resize(int n) {
lab.assign(n, -1);
}
int find_set(int p) {
return lab[p] < 0 ? p : lab[p] = find_set(lab[p]);
}
bool same_set(int u, int v) {
return find_set(u) == find_set(v);
}
bool join(int u, int v) {
u = find_set(u), v = find_set(v);
if (u != v) {
if (lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v], lab[v] = u;
return true;
}
return false;
}
};
const int N = 500 + 5;
int side[N];
vii adj[N];
void dfs(int type, int u, int fa) {
side[u] = type;
for (auto [v, id] : adj[u]) if (v != fa) {
dfs(type, v, u);
}
}
vector<int> find_roads(int n, vector<int> U, vector<int> V) {
// m: not golden, m+1: golden
int m = U.size();
DSU tree(n); vector<int> treeEdges;
for (int i = 0; i < m; ++i) {
if (tree.join(U[i], V[i])) {
treeEdges.emplace_back(i);
adj[U[i]].emplace_back(V[i], i);
adj[V[i]].emplace_back(U[i], i);
}
}
int numGolden = count_common_roads(treeEdges);
DSU dsu(m + 2);
for (auto e : treeEdges) {
dfs(0, U[e], V[e]);
dfs(1, V[e], U[e]);
vector<int> edges;
for (int i = 0; i < m; ++i) if (i != e) {
if (side[U[i]] != side[V[i]]) edges.emplace_back(i);
}
vector<int> tmp;
for (auto id : treeEdges)
if (id != e) tmp.emplace_back(id);
for (auto id : edges) if (dsu.same_set(id, m) || dsu.same_set(id, m + 1)) {
tmp.emplace_back(id);
int cnt = count_common_roads(tmp);
if (numGolden == cnt) dsu.join(e, id);
else {
if (dsu.same_set(id, m)) dsu.join(e, m + 1);
else dsu.join(e, m);
}
break;
}
if (dsu.same_set(e, m) || dsu.same_set(e, m + 1)) continue;
shuffle(edges.begin(), edges.end(), rng);
for (auto id : edges) {
tmp.emplace_back(id);
int cnt = count_common_roads(tmp);
if (numGolden == cnt) dsu.join(e, id);
else {
if (numGolden < cnt) dsu.join(e, m), dsu.join(id, m + 1);
else dsu.join(e, m + 1), dsu.join(id, m);
break;
}
}
}
vector<int> ans;
for (int i = 0; i < m; ++i)
if (dsu.same_set(i, m + 1)) ans.emplace_back(i);
return ans;
}
#ifdef hwe
signed main() {
cin >> n >> m;
u.resize(m);
v.resize(m);
for(int i = 0; i < m; i++)
cin >> u[i] >> v[i];
goal.resize(m, false);
for(int i = 0; i < n - 1; i++) {
int id;
cin >> id;
goal[id] = true;
}
vector<int> res = find_roads(n, u, v);
if(_count_common_roads_internal(res) != n - 1)
wrong_answer();
cout << "YES\n";
return 0;
}
#endif
