Подобається

Ви помітили, що якщо видалити літеру 'k' зі слова "like" і зробити всі циклічні зсуви, то одним із них буде "eli"? Це може стати хорошим завданням, однак тут ви не будете займатися ні словами, ні циклічними зсувами.

Еллі зіткнулася з великою проблемою. Нещодавно її (не без підстав) звинуватили в тому, що вона подобається всім хлопцям у її класі (якщо не зважати на інших дівчат), а вона, зі свого боку, не звертає уваги на хлопців. Це звинувачення було зроблено головним чином тому, що деякі з її однокласників заздрили, що вона набагато більш улюблена, ніж вона любить інших. З іншого боку, Еллі виступає проти стосунків - це також причина, чому вона ігнорує хлопців у своєму класі. Більше того - вона була б щаслива, якби навколо неї було якомога менше пар у стосунках "подобається".

Щоб уникнути конфліктів у майбутньому, вона вирішила переконатися, що для кожної людини в школі має місце наступне: кількість людей, які подобаються йому, відрізняється від числа людей, яким він подобається, не більше ніж на $1$. Переклавши це на більш природну мову, ми отримаємо, що кожна людина є вершиною в графі, а факт того, що $A$ любить $B$, задається орієнтованим ребром. Таким чином Еллі хоче, щоб кількість вхідних ребер відрізнялася від числа вихідних ребер не більше ніж на $1$.

Вона вирішила використати свою чарівність та дипломатію (також відому як обман і маніпуляція), щоб досягти цього. Еллі знає всі пари людей у школі, які знають один одного (що ми можемо вважати неорієнтованим ребром на графі). Вона може змусити будь-яку пару знайомих змінити свої стосунки, щоб один з них почав любити іншого або навпаки, але не обидва одночасно (не забувайте, що вона проти того, щоб мати пари в школі). Вона хоче виконати свій злий план, "орієнтуючи" всі ребра на графі, тобто кожне знайомство стає одностороннім стосунком.

Ви вирішили перевірити, чи зможе вона це зробити, і чи зможе вона показати одну з можливих орієнтацій ребер.