21550번 - Гаджеты на дереве 서브태스크스페셜 저지다국어

Вася недавно придумал новое развлечение. Пусть дан связный ориентированный граф, состоящий из $n$ вершин и $2 \cdot (n - 1)$ рёбер, причём для каждого ребра $(u, v)$, существует ребро $(v, u)$. Иначе говоря, граф был получен из дерева, в котором каждое ребро было расщеплено на два противоположных ребра, ориентированных в разные стороны.

Назовем гаджетом такую пару рёбер $(e_1, e_2)$, что конец $e_1$ совпадает с началом $e_2$ или наоборот (в частности, два противоположных друг другу ребра --- гаджет). Вася развлекается тем, что разбивает рёбра графа на непересекающиеся гаджеты. Конечно, ему легко удалось это сделать с  исходным графом.

Васин друг Петя удалил из дерева $2 \cdot k$ ориентированных рёбер. Таким образом, в графе осталось $m = 2 \cdot (n - 1) - 2 \cdot k$ ориентированных ребер. 

Теперь Вася хочет узнать, можно ли разбить оставшиеся ребра на непересекающиеся гаджеты, и, если можно, --- найти это разбиение. Помогите ему!

Рис. 1: Разбиение на гаджеты в первом примере

В первой строке даны два целых числа $n$ и $m$ ($2 \le n \le 150\,000$, $2 \le m \le 2n-2$) --- число вершин и число оставшихся рёбер. Гарантируется, что число $m$ чётное. 

В следующих $m$ строках даны по два числа $u_i, v_i$ ($1 \le u_i, v_i \le n$) --- начала и концы оставшихся рёбер.

Если разбить рёбра на гаджеты нельзя, выведите <<No>>. 

В противном случае выведите <<Yes>>, а затем выведите $\frac{m}{2}$ строк по 4 числа в каждой --- пары рёбер в каждом из гаджетов. Каждое ребро описывается двумя числами: своим началом и концом.

Разбиение на гаджеты в первом примере изображено на рисунке в условии.

Обратите внимание, что в этой задаче размер входных данных может быть большим. Рекомендуем ознакомиться с разделом <<Скорость ввода и выбор ОС>> в памятке участника.