EduBrick

B. Проверить порядок

1000 мс · 256 МБ · всё или ничего

Дан ориентированный ациклический граф и перестановка его вершин. Проверьте, является ли эта перестановка топологической сортировкой.

Формат ввода

В первой строке - числа nn и mm (1≤n,m≤1051 \le n, m \le 10^5).

В следующих mm строках - рёбра uiu_i, viv_i ациклического графа. В последней строке - перестановка из nn чисел.

Формат вывода

Выведите YES, если перестановка является топологической сортировкой, и NO иначе.

Примеры

ввод
3 3
2 3
1 3
1 2
2 1 3
вывод
NO
ввод
3 3
3 2
1 2
3 1
3 1 2
вывод
YES
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.