| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 62 | 25 | 24 | 41.379% |
Вася недавно придумал новое развлечение. Пусть дан связный ориентированный граф, состоящий из $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 числа в каждой --- пары рёбер в каждом из гаджетов. Каждое ребро описывается двумя числами: своим началом и концом.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $ n \le 20 ,ドル $m \le 20$ |
| 2 | 10 | $n \le 200$ |
| 3 | 11 | $n \le 3000,ドル $m = 2n - 4$ |
| 4 | 29 | $n \le 3000$ |
| 5 | 11 | $n \le 150,000円,ドル $m = 2n - 4$ |
| 6 | 32 | $n \le 150,000円$ |
5 6 1 2 2 1 1 5 2 3 2 4 4 2
Yes 1 2 2 3 2 1 1 5 2 4 4 2
4 4 2 1 2 3 2 4 4 2
No
4 4 1 2 2 1 3 4 4 3
Yes 1 2 2 1 3 4 4 3
Разбиение на гаджеты в первом примере изображено на рисунке в условии.
Обратите внимание, что в этой задаче размер входных данных может быть большим. Рекомендуем ознакомиться с разделом <<Скорость ввода и выбор ОС>> в памятке участника.
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics 2021 6번