Планування польоту
Авіакомпанія "NCPC Авіалінії" здійснює польоти між n містами, пронумерованими від 1 до n, по всьому світу. Проте, у неї є лише n - 1 різних рейсів (в обох напрямках), тому для подорожі між будь-якими двома містами доводиться користуватися кількома рейсами. Оскільки менеджмент переконався, що існує можливість подорожувати між будь-якими двома містами, то існує точно одна множина рейсів, якими може скористатися пасажир для переміщення між двома містами (вважаючи, що Ви скористаєтесь лише однією авіалінією).
Останнім часом у NCPC Авіалініях багато часто літаючих пасажирів скаржилися, що їм доводиться занадто часто змінювати рейси, щоб дістатися до кінцевого пункту призначення. Оскільки NCPC Авіалінії не хочуть втратити своїх клієнтів, і при цьому зберегти зручність своїх рейсів, вони вирішили скасувати один зі своїх рейсів і замінити його іншим. Допоможіть авіакомпанії написати програму, яка допоможе знайти рейс, який слід скасувати, а також новий рейс, який слід додати, щоб максимальна кількість зміни рейсів пасажиром при подорожі між парами міст, які обслуговують NCPC Авіалінії, була мінімальною.
Вхідні дані будуть такими, що завжди можна покращити максимальну кількість зміни рейсів.
Вхідні дані
Перша стрічка містить кількість міст n (4 ≤ n ≤ 2500) в авіалініях NCPC. Наступні n - 1 стрічок описують рейси. Кожен рейс задається парою міст a і b (1 ≤ a, b ≤ n).
Вихідні дані
Виведіть три стрічки. Перша стрічка містить найменшу кількість рейсів, яке слід змінити при подорожі між парами міст після зміни одного з рейсів. Друга стрічка містить номери міст скасованого рейсу. Третя стрічка містить номери міст, між якими буде додано новий рейс.
Якщо існує декілька рішень, виведіть будь-яке.