У Тридев'ятому Царстві було \(N\) міст, деякі з яких були з'єднані дорогами. На жаль, останнім часом дістатися з одного міста в інше стало дуже складно через автомобільні пробки. З метою боротьби з пробками було вирішено всі дороги зробити односторонніми, тобто. дозволити проїзд кожною дорогою тільки в одному напрямку. При цьому потрібно, щоб, як і раніше, можна було з будь-якого міста потрапити до будь-якої іншої.

Формат вхідних даних

У вхідному потоці записано спочатку число \(N\) – кількість міст \((1 ≤N≤1000)\).

Потім записано число \(M\) – кількість доріг \((1≤M≤100000)\).

Далі йде \(M\) пар чисел, що задають дороги (кожна дорога описується номерами міст, які вона з'єднує). Не буває доріг із деякого міста до того ж міста. Між двома містами може бути кілька доріг. Гарантується, що до запровадження одностороннього руху можна було потрапити з будь-якого міста до будь-якого іншого.

Формат вихідних даних

У вихідний потік потрібно видати M пар чисел, що відповідають дорогам (дороги мають бути видані в тому самому порядку, в якому вони задані у вхідному файлі). Для кожної дороги спочатку має бути записаний номер міста, з якого по ній можна буде виїхати після одностороннього руху, а потім — номер міста, куди ця дорога веде.

Якщо ввести односторонній рух так, щоб можна було з будь-якого міста потрапити в будь-яке інше, не можна, вихідний файл повинен містити одне число 0.

Приклад вхідних даних-1

4
6
1 2
1 2
2 3
2 4
4 3
1 4

Приклад вихідних даних-1

2 1
2 1
3 2
4 2
4 3
1 4

Приклад вхідних даних-2

2
1
1 2

Приклад вихідних даних-2

0