У Берляндії незабаром з'являться свої авіалінії. Комітет із розробки берляндських авіаліній вже запропонував свій варіант з'єднання міст авіарейсами. Кожен авіарейс задається парою різних міст. Рейси односторонні. Президентові сподобався план, проте він здався йому надто неекономним. Потрібно розробити новий план, який містить найменшу кількість авіарейсів та задовольняє умові: - якщо з міста \(a\) можна було потрапити до міста \(b\) (можливо, з пересадками) згідно з початковим планом, то й у новому плані це має бути можливим.

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

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

У першому рядку записані цілі числа \(𝑁\) і \(𝑀\) (\(1≤𝑁≤1000\) , \(0≤𝑀≤10000\) ), де \(𝑁\) – кількість міст у країні, а \(𝑀\) – кількість авіарейсів у початковому плані. Міста нумеруються від 1 до \(𝑁\).

Далі записано \(𝑀\) пар різних чисел \(𝑎_𝑖\) , \(𝑏_𝑖\) що позначають наявність рейсу з \(𝑎_𝑖\) до \(𝑏_𝑖\) в первісному плані (\(1≤𝑎_𝑖≤𝑁\) , \(1≤𝑏_𝑖≤N\)). Пари розділяються пробілами чи переведенням рядків. Між парою міст може бути більше одного авіарейсу.

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

У першому рядку виведіть кількість рейсів у новому плані.

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

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

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

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

4
1 3 3 2 2 1 2 4