| Codeforces Round 296 (Div. 2) |
|---|
| Закончено |
Проектируемый дата-центр одной Большой Софтверной Компании состоит из n компьютеров, соединённых m проводами. Упрощённо каждый компьютер можно считать коробкой, из которой торчит несколько проводов. По каждому проводу в одном из двух направлений может течь Очень Важная Информация. Так как план дата-центра ещё не утверждён, для каждого провода пока не определено, в каком направлении по нему будет идти информация. Провода проложены таким образом, что каждый компьютер был связан с каждым, возможно, через некоторые другие компьютеры.
За порядок в дата-центре будет отвечать уборщица Клавдия Ивановна, которая любит собирать провода в пучки с помощью стяжек. По известным ей одной причинам, она группирует провода, торчащие из компьютера, по два, а если вдруг этого не получается, то она в ярости заливает компьютер водой из ведра.
Следует также отметить, что из-за специфических физических характеристик Очень Важной Информации, категорически запрещается связывать в пучок два провода, по которым информация течёт в разные стороны.
Руководство дата-центра хочет определить, как следует направить информацию по каждому проводу таким образом, чтобы Клавдия Ивановна имела возможность сгруппировать по два все провода, исходящие из каждого компьютера, соблюдая условие выше. Так как это может быть невозможно с имеющимся планом соединений, вам разрешается добавить минимально возможное количество проводов в схему, после чего требуется определить направление потока информации по каждому проводу (да, иногда дата-центры проектируются, исходя из удобства уборщиц...)
В первой строке следуют два числа n и m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000) — количество компьютеров и количество имеющихся проводов соответственно.
В каждой из последующих строк следует по два числа ai, bi (1 ≤ ai, bi ≤ n) — номера компьютеров, соединённых i-м проводом. Дата-центры частенько бывают очень сложно устроены, поэтому между парой компьютеров может быть больше одной пары проводов, а некоторые провода могут соединять компьютер с самим собой.
В первой строке выведите единственное число p (p ≥ m) — минимальное количество проводов в итоговой схеме.
В каждой из последующих p строк выведите по паре чисел ci, di (1 ≤ ci, di ≤ n), описывающей очередной провод. Подобная запись означает, что информация будет течь по очередному проводу в направлении от ci к di.
Среди выведенных вами проводов должны фигурировать все имеющиеся в плане провода в том или ином направлении. Гарантируется, что существует решение, в котором p не превосходит 500 000.
Если возможных ответов с минимальным значением p несколько, выведите любой.
4 6
1 2
2 3
3 4
4 1
1 3
1 3
6
1 2
3 4
1 4
3 2
1 3
1 3
3 4
1 2
2 3
1 1
3 3
6
2 1
2 3
1 1
3 3
3 1
1 1
Иллюстрация к первому тесту из условия. Объединённые пары проводов изображены исходящими из одной точки.
Иллюстрация ко второму тесту из условия. Добавленные провода отмечены жирным.
Альтернативный вариант ответа на второй тест из условия:
