시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB37161544.118%

문제

Вася недавно придумал новое развлечение. Пусть дан связный ориентированный граф, состоящий из $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 числа в каждой --- пары рёбер в каждом из гаджетов. Каждое ребро описывается двумя числами: своим началом и концом.

서브태스크

번호배점제한
17

$ n \le 20 $, $m \le 20$

210

$n \le 200$

311

$n \le 3000$, $m = 2n - 4$

429

$n \le 3000$

511

$n \le 150\,000$, $m = 2n - 4$

632

$n \le 150\,000$

예제 입력 1

5 6
1 2
2 1
1 5
2 3
2 4
4 2

예제 출력 1

Yes
1 2 2 3
2 1 1 5
2 4 4 2

예제 입력 2

4 4
2 1
2 3
2 4
4 2

예제 출력 2

No

예제 입력 3

4 4
1 2
2 1
3 4
4 3

예제 출력 3

Yes
1 2 2 1
3 4 4 3

힌트

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

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

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.