Карим является управляющим одного небольшого города. Дорожная система в этом городе состоит из $$$n$$$ перекрёстков и $$$m$$$ дорог. Каждая дорога соединяет два различных перекрестка, и между двумя перекрестками проходит не более одной дороги. Все дороги являются двусторонними.
В городе обажают кататься на автомобилях. Поэтому если по дорогам можно наматывать круги, то любой автомобилист с удовольстивем будет кататься до самого вечера. Такая ситуация не устраивает Карима, так как дороги таким образом очень быстро портятся.
Карим понял, что он может ориентировать каждую дорогу в какую-то сторону и таким образом избавиться от циклом. Сам Карим не справился с этой задачей, поэтому просит вас ориентировать каждую дорогу так, чтобы в городе больше нельзя было бесконечно передвигаться по дорогам.
Если есть несколько вариантов ответа, то выведите любой из них.
Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ $$$(1 \le n \le 2 \cdot 10^5, n - 1 \le m \le min(\frac{n(n - 1)}{2}, 2 \cdot 10^5))$$$ — количество перескрестков и дорог соответственно.
Следующие $$$m$$$ строк входных данных содержат описание дорог, по два целых числа $$$u$$$ и $$$v$$$ $$$(1 \le u,v \le n, u \neq v)$$$ — номера перекрестков, соединённых дорогой. Гарантируется, каждая дорога соединяет разные перекрестки и любые два перекрестка соединяет максимум одна дорога.
Выведите $$$m$$$ пар чисел — получившиеся ориентированные дороги. Для каждой дороги выведите два числа — начало и конец дороги соответственно.
Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.
| Группа | Баллы | Дополнительные | Необх. группы | Комментарий |
| ограничения | ||||
| 0 | 0 | – | – | Тесты из условия. |
| 1 | ? | – | ||
| 2 | ? | – | ||
| 3 | ? | – |
4 4 1 2 3 2 2 4 4 3
2 1 3 2 4 2 4 3
Иллюстрация к примеру:
