У Казака Вуса есть простой граф из \(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\). Другими словами, нужно чтобы степень каждой вершины уменьшилась на не более чем в два раза.
Помогите Вусу оставить правильное количество ребер!
Выходные данные
В первой строке выведите одно целое число \(k\) (\(0 \leq k \leq \lceil \frac{n+m}{2} \rceil\)) — количество ребер, которые нужно оставить.
В каждой из следующих \(k\) строк выведите по два целых числа \(u_i\) и \(v_i\) (\(1 \leq u_i, v_i \leq n\)) — вершины, ребро между которыми нужно оставить. Нельзя выводить одно и то же ребро два или более раза.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|