G. Истоки и стоки
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан ацикличный ориентированный граф, состоящий из $$$n$$$ вершин и $$$m$$$ ребер. Граф не содержит кратных ребер и петель.

Вершина называется истоком, если в нее не входит ребер. Вершина называется стоком, если из нее не исходит ребер. Эти определения подразумевают, что некоторые вершины могут быть одновременно истоком и стоком.

Количество истоков в графе равно количеству стоков, и это число не превосходит $$$20$$$.

К графу применяется следующий алгоритм:

  1. если в графе нет истоков и стоков, то выйти;
  2. выбрать произвольный исток $$$s$$$, произвольный сток $$$t$$$, добавить ребро из $$$t$$$ в $$$s$$$ в граф и перейти к шагу $$$1$$$ (эта операция удаляет $$$s$$$ из истоков и $$$t$$$ из стоков). Обратите внимание, что $$$s$$$ и $$$t$$$ могут быть одной и той же вершиной, тогда добавляется петля.

В конце проверяется, стал ли граф сильно связным (любая вершина достижима из любой другой).

Ваша задача — проверить, что граф становится сильно связным вне зависимости от выбора истоков и стоков на втором шаге алгоритма.

Входные данные

В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^6$$$) — количество вершин и количество ребер в графе, соответственно.

В каждой из следующих $$$m$$$ строк записаны по два целых числа $$$v_i, u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$v_i \ne u_i$$$) — описание $$$i$$$-го ребра изначального графа.

Гарантируется, что количество истоков равно количеству стоков, и это число не превышает $$$20$$$. Гарантируется, что граф не содержит кратных ребер. Гарантируется, что граф не содержит циклов.

Выходные данные

Выведите «YES», если граф становится сильно связным вне зависимости от выбора истоков и стоков на втором шаге алгоритма. В противном случае выведите «NO».

Примеры
Входные данные
3 1
1 2
Выходные данные
NO
Входные данные
3 3
1 2
1 3
2 3
Выходные данные
YES
Входные данные
4 4
1 2
1 3
4 2
4 3
Выходные данные
YES