Миша тренирует несколько ACM-команд в одном вузе. Он опытный тренер и понимает, как важна на тренировках атмосфера сотрудничества и взаимопомощи. Все так и было, пока одна команда не начала побеждать на контестах чаще остальных и слегка не зазналась. Это не способствует созданию позитивной атмосферы, необходимой для продуктивной тренировки. Но Миша знает, что делать!

К нему на тренировку ходят k команд по три человека. Увы, команды не всегда тренируются в полном составе, но присылают как минимум одного представителя. На следующей тренировке Миша разобьёт всех пришедших на n пар так, чтобы в каждой оказались представители разных команд. Игроки из одной пары сыграют друг против друга мини-контест.

Мише нужно, чтобы во всех мини-контестах победили представители разных команд. Чтобы это организовать, он готов пойти на хитрости в определении победителей в каждой паре. Сможет ли Миша добиться желаемого?

В первой строке записано два числа — n и k (1 ≤ n ≤ 10⁵, 2 ≤ k ≤ 10⁵). Далее располагается n строк. В i-й из них записаны два числа x_i, y_i (1 ≤ x_i, y_i ≤ k; x_i ≠ y_i) — номера команд, представители которых составляют пару с номером i.

Гарантируется, что каждая команда представлена не менее чем в одной и не более чем в трех парах.

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

Если у Миши нет шансов, то в единственной строке следует вывести No.