У Казака Вуса есть простой граф из \(n\) вершин и \(m\) ребер. Пусть \(d_i\) — степень \(i\)-й вершины. Напомним, что степень вершины \(i\) — это количество прилагаемых ребер к вершине \(i\).
Ему нужно оставить не более \(\lceil \frac{n+m}{2} \rceil\) ребер. Пусть \(f_i\) — степень \(i\)-й вершины после удаления. Нужно удалить ребра так, чтобы \(\lceil \frac{d_i}{2} \rceil \leq f_i\) для каждого \(i\). Другими словами, нужно чтобы степень каждой вершины уменьшилась на не более чем в два раза.
Помогите Вусу оставить правильное количество ребер!
Первая строка содержит два целых числа \(n\) и \(m\) (\(1 \leq n \leq 10^6\), \(0 \leq m \leq 10^6\)) — количество вершин и ребер соответственно.
Каждая из следующих \(m\) строк содержит два целых числа \(u_i\) и \(v_i\) (\(1 \leq u_i, v_i \leq n\)) — вершины, между которыми находиться ребро.
Гарантируется, что в графе нет петель и кратных ребер.
В первой строке выведите одно целое число \(k\) (\(0 \leq k \leq \lceil \frac{n+m}{2} \rceil\)) — количество ребер, которые нужно оставить.
В каждой из следующих \(k\) строк выведите по два целых числа \(u_i\) и \(v_i\) (\(1 \leq u_i, v_i \leq n\)) — вершины, ребро между которыми нужно оставить. Нельзя выводить одно и то же ребро два или более раза.
6 6 1 2 2 3 3 4 4 5 5 3 6 5
5 2 1 3 2 5 3 5 4 6 5
10 20 4 3 6 5 4 5 10 8 4 8 5 8 10 4 9 5 5 1 3 8 1 2 4 7 1 4 10 7 1 7 6 1 9 6 3 9 7 9 6 2
12 2 1 4 1 5 4 6 5 7 1 7 4 8 3 8 5 9 3 9 6 10 4 10 7
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач