Задача H. Киберспортивный турнир ≡

Условие

Ура! Влад закончил создание своей собственной игры в виртуальной реальности. Для продвижения игры он собирается провести турнир, в котором примут участие N киберспортсменов. Турнир будет проходить по следующей системе: в каждом туре выбирается пара игроков, выигравший остаётся в турнире, а проигравший выбывает. В конце турнира остаётся один игрок — победитель.

В игре присутствуют некоторые проблемы с производительностью, и Влад об этом знает. Он хочет, чтоб потенциальные покупатели игры увидели игру в лучшем свете. Поэтому Влад подобрал M таких пар игроков a_i и b_i, что игрок c номером a_i всегда побеждает игрока с номером b_i, и во время матчей в этих парах не возникает проблем с производительностью. Во избежание непредвиденных ситуация он хочет так составить расписание турнира так, чтобы он знал победителей всех матчей заранее и в конце турнира остался ровно один игрок.

Формат входного файла

Первая строка входного файла содержит числа N и M. Следующие M строк содержат пары чисел a_i и b_i. Гарантируется, что не существует такой пары i и j, что a_i = b_j и b_i = a_j.

Формат выходного файла

Если невозможно провести турнир так, как хочет Влад, необходимо вывести No. Иначе первая строка выходного файла должна содержать Yes, а следующие далее N − 1 строк — описание матчей в порядке их проведения. По два числа на строку: первое число — номер победившего в очередном матче игрока, второе число — номер проигравшего игрока. Если существует несколько правильных ответов, выведите любой из них.

Ограничения

2 ≤ N ≤ 100000, 0 ≤ M ≤ 500000, 1 ≤ a_i, b_i ≤ N

Примеры тестов

3 3
1 2
2 3
3 1

Yes
1 2 
3 1

5 4
1 2
2 3
3 4
4 5

Yes
4 5
3 4
2 3
1 2

4 2
1 2
3 4

No

2 0

No

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Yes
3 4
2 3
1 2

7 8
1 2 
2 3
3 1
4 1
4 5
5 6
6 7
7 5

Yes
2 3
1 2
4 1
6 7
5 6
4 5