#include "simurgh.h"
/*
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
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);
}
*/
#include <bits/stdc++.h>
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
const int m = (int)u.size();
std::vector<int> edgeType(m, -1);
for (int i = 0; i < n; ++i) {
std::vector<int> e1, e2;
for (int j = 0; j < m; ++j) {
if (u[j] == i or v[j] == i) {
e1.push_back(j);
} else {
e2.push_back(j);
}
}
std::vector<std::vector<std::pair<int, int>>> graph(n);
for (const int x : e2) {
graph[u[x]].push_back({v[x], x});
graph[v[x]].push_back({u[x], x});
}
std::vector<bool> isSeen(n);
int cnt = 0;
std::vector<int> id(n), treeEdges;
for (int f = 0; f < n; ++f) {
if (isSeen[f]) continue;
if (f == i) continue;
std::queue<int> que;
que.push(f);
isSeen[f] = true;
while (not que.empty()) {
const int x = que.front();
que.pop();
id[x] = cnt;
for (const auto &[t, y] : graph[x]) {
if (not isSeen[t]) {
treeEdges.push_back(y);
que.push(t);
isSeen[t] = true;
}
}
}
++cnt;
}
const int R = cnt;
std::vector<std::vector<int>> eDivided(R);
for (const int x : e1) {
if (u[x] == i) {
eDivided[id[v[x]]].push_back(x);
} else {
eDivided[id[u[x]]].push_back(x);
}
}
for (int f = 0; f < R; ++f) {
const auto &vec = eDivided[f];
const int T = (int)vec.size();
for (int j = 0; j < R; ++j) {
if (j != f) {
treeEdges.push_back(eDivided[j][0]);
}
}
std::vector<int> vals(T);
for (int j = 0; j < T; ++j) {
treeEdges.push_back(vec[j]);
vals[j] = count_common_roads(treeEdges);
treeEdges.pop_back();
}
const int ma = *std::max_element(vals.begin(), vals.end());
for (int j = 0; j < T; ++j) {
if (vals[j] == ma) {
edgeType[vec[j]] = 1;
} else {
edgeType[vec[j]] = 0;
}
}
for (int j = 0; j < R - 1; ++j) {
treeEdges.pop_back();
}
}
}
std::vector<int> ret;
for (int i = 0; i < m; ++i) {
if (edgeType[i] == 1) {
ret.push_back(i);
}
}
return ret;
}
/*
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;
}
*/
