Планування польоту#548
NCPC Airways здійснює рейси між містами, пронумерованими від до . Проте авіакомпанія має лише n - 1 різних рейсів (які здійснюються в обох напрямках), тож для подорожі між будь-якими двома містами може знадобитися скористатися кількома рейсами. Керівництво подбало про те, щоб дістатися будь-якої пари міст було можливо, використовуючи рівно один набір рейсів (за умови, що ви користуєтеся лише рейсами NCPC Airways).
Нещодавно часті мандрівники почали скаржитися, що їм доводиться надто часто пересідати, щоб дістатися до кінцевого пункту призначення. Щоб утримати своїх клієнтів і забезпечити зручніші пересадки, NCPC Airways вирішила скасувати один із рейсів і замінити його новим. Напишіть програму, яка допоможе авіакомпанії визначити, який рейс потрібно скасувати, а який — додати, щоб мінімізувати максимальну кількість пересадок, необхідних для подорожі між будь-якою парою міст.
Вхід завжди такий, що максимальну кількість пересадок можна зменшити.
Перший рядок містить ціле число (4 \le n \le 2500) — кількість міст. Наступні n-1 рядків описують рейси парами міст і (1 \le a, b \le n).
Виведіть три рядки. У першому рядку — мінімально можливу максимальну кількість рейсів, необхідних для подорожі між будь-якою парою міст після зміни одного рейсу. У другому рядку — номери двох міст, рейс між якими потрібно скасувати. У третьому рядку — номери двох міст, між якими слід додати новий рейс.
Якщо існує кілька оптимальних розв'язків, можна вивести будь-який із них.
Приклад 1