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

Автор:И. Блинов, А. Жихарева   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 100000, 0 ≤ M ≤ 500000, 1 ≤ ai, bi ≤ N

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3
1 2
2 3
3 1
Yes
1 2 
3 1
2
5 4
1 2
2 3
3 4
4 5
Yes
4 5
3 4
2 3
1 2
3
4 2
1 2
3 4
No
4
2 0
No
5
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Yes
3 4
2 3
1 2
6
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

0.147s 0.016s 15