Виявник глухого кута

Рада Вашого рідного міста вирішила покращити розміщення дорожніх знаків, особливо в тупиках. Вони надали Вам дорожню карту, і Ви повинні визначити, де встановити знаки, щоб позначити тупики. Завдання полягає в тому, щоб використати якомога менше знаків.

Дорожня карта складається з набору перехресть, з'єднаних вулицями з двостороннім рухом. Наступне правило описує, як визначити повне розміщення знаків тупика. Розглянемо вулицю $S$, що з'єднує місце $x$ з іншим місцем. Вхід у $S$ з боку $x$ стає тупиковим, якщо після входу в $S$ з $x$ неможливо повернутися в $x$, не роблячи розворот. Розворот — це поворот на $180$ градусів, що одразу змінює напрямок.

Щоб зменшити витрати, Ви вирішили не встановлювати зайві знаки тупика, як зазначено в наступному правилі. Розглянемо вулицю $S$ зі знаком тупика на в'їзді з боку $x$ та іншу вулицю $T$ зі знаком тупика на в'їзді з боку $y$. Якщо після в'їзду в $S$ з $x$ можна досягти $y$ і в'їхати в $T$, не роблячи розворот, то знак тупика на в'їзді з боку $y$ вулиці $T$ є зайвим. Див. приклади на рисунку E.1.

Рисунок E.1: Ілюстрація вхідних даних з прикладом розміщення незайвих знаків тупика.

Вхідні дані

Перший рядок містить два цілих числа $n$ і $m$, де $n(1\le n\le 5\cdot 10^5)$ — кількість перехресть, а $m(0\le m\le 5\cdot 10^5)$ — кількість вулиць. Кожен з наступних $m$ рядків містить два цілих числа $v$ і $w(1\le v<w\le n)$, що вказують на те, що вулиця з двостороннім рухом з'єднує перехрестя $v$ і $w$. Усі вулиці у вхідних даних різні.

Вихідні дані

У першому рядку виведіть кількість $k$ встановлених тупикових знаків. У кожному з наступних $k$ рядків виведіть два цілих числа $v$ і $w$, що вказують на те, що на в'їзді з боку $v$ на вулицю, що з'єднує перехрестя $v$ і $w$, необхідно встановити знак тупика. Рядки, що описують тупикові знаки, повинні бути відсортовані в порядку зростання $v$, а при рівних значеннях — в порядку зростання $w$.

Приклади