F. Казак Вус и граф
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Казака Вуса есть простой граф из $$$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