ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2089. Опытный тренер

Ограничение времени: 2.0 секунды
Ограничение памяти: 256 МБ
Миша тренирует несколько ACM-команд в одном вузе. Он опытный тренер и понимает, как важна на тренировках атмосфера сотрудничества и взаимопомощи. Все так и было, пока одна команда не начала побеждать на контестах чаще остальных и слегка не зазналась. Это не способствует созданию позитивной атмосферы, необходимой для продуктивной тренировки. Но Миша знает, что делать!
К нему на тренировку ходят k команд по три человека. Увы, команды не всегда тренируются в полном составе, но присылают как минимум одного представителя. На следующей тренировке Миша разобьёт всех пришедших на n пар так, чтобы в каждой оказались представители разных команд. Игроки из одной пары сыграют друг против друга мини-контест.
Мише нужно, чтобы во всех мини-контестах победили представители разных команд. Чтобы это организовать, он готов пойти на хитрости в определении победителей в каждой паре. Сможет ли Миша добиться желаемого?

Исходные данные

В первой строке записано два числа — n и k (1 ≤ n ≤ 105, 2 ≤ k ≤ 105). Далее располагается n строк. В i-й из них записаны два числа xi, yi (1 ≤ xi, yik; xiyi) — номера команд, представители которых составляют пару с номером i.
Гарантируется, что каждая команда представлена не менее чем в одной и не более чем в трех парах.

Результат

Если Миша сможет добиться успеха, то в первой строке следует вывести Yes. В каждой из следующих n строк вывести по одному числу — номеру команды, которая должна победить в соответствующей паре. Если ответов несколько, выведите любой.
Если у Миши нет шансов, то в единственной строке следует вывести No.

Примеры

исходные данныерезультат
3 4
1 2
2 3
1 4
Yes
2
3
4
6 4
1 2
1 3
1 4
2 3
2 4
3 4
No
Автор задачи: Александр Ипатов, подготовка — Егор Щелконогов