Like
Есенен Турнир по Информатика 2010
Time Limit: 0.8s, Memory Limit: 64MiB
Забелязали ли сте, че ако премахнем буквата 'k' от думата "like" и направим всички циклични ротации, една от тях е "eli"? От това би излязло страхотна задача! За Ваша радост, тази няма нищо общо нито с думи, нито с циклични ротации.

Ели е изправена пред голям проблем. Наскоро тя беше обвинена (не твърде неправомерно), че всички момчета в класа я харесват и не обръщат внимание на останалите момичета, докато тя самата не обръща внимание на никое от момчетата. Това твърдение беше породено от завистта на някои от нейните съученички, че тя е много по-харесвана, отколкото самата тя харесва. Ели, от друга страна, е твърдо против връзките. Всъщност тя би искала да има възможно най-малко щастливи двойки около себе си.

За да не си навлича неприятности в бъдеще, Ели е решила да направи така, че за всеки човек от училището да е изпълнено, че броят хора, които го харесват се различава от броя хора, които той харесва, с не повече от 1. Казано на по-човешки език, ако си представим всеки ученик като връх в граф и свойството, че човекът А харесва човека B като насочено ребро от A към B, то за всеки връх от графа трябва да е изпълнено, че абсолютната стойност на разликата на входящите и изходящите ребра е по-малка или равна на 1.

За целта тя е решила да използва своите добродетели чар и дипломатичност (също познати като измама и манипулация). Елеонора знае всички двойки ученици, които се познават (които можем да считаме като ненасочени ребра в графа). Тя може да "подтикне" някоя двойка познати по такъв начин, че единият да започне да харесва другия или обратно, но не и двете едновременно (все пак не забравяйте, че тя е против двойките). Момичето иска да изпълни пъкления си план, "насочвайки" всички ребра – тоест всяко познанство да се превърне в едностранно харесване.

Вие решавате да проверите дали тя може да направи това, и ако е възможно – да покажете едно от възможните насочвания на ребрата.
Вход
На първия ред на стандартния вход ще бъдат зададени числата N и M, съответно броят ученици в училището и броят познанства между тях. На всеки от следващите М реда ще има по една двойка числа Pi и Pj, указваща, че съответните ученици се познават. Всяка двойка ученици ще присъства най-много веднъж във входа. Всички числа във входа са цели и положителни.
Изход
На първия ред на стандартния изход изведете "Yes", ако такова насочване на ребрата е възможно и "No" в противен случай. Ако отговорът е "Yes" изведете М реда с двойки числа Pi и Pj, които този път показват, че Pi харесва Pj. Ако съществува повече от едно такова насочване, изведете кое да е от тях.
Ограничения
  • 1 ≤ N ≤ 1,000
  • 1 ≤ M ≤ 100,000
  • 1 ≤ Pi, PjN
Примерен Вход Примерен Изход
5 7 1 2 1 3 4 1 1 5 3 2 4 5 3 5 Yes 1 2 3 1 4 1 1 5 2 3 5 4 3 5
В училището има 5 ученика и 7 познанства между тях. След насочването на ребрата всеки ученик е харесван и харесва по равен брой пъти, с изключение на 3, който харесва с едно повече, и 5, който бива харесван с едно повече.
Мрън!