Авиакомпания "NCPC Авиалинии" выполняет полеты между n городами, пронумерованными от 1 до n, по всему миру. Однако у нее имеется только n - 1 различных рейсов (в обоих направлениях), поэтому для путешествия между любыми двумя городами приходится пользоваться несколькими рейсами. Поскольку менеджмент убедился, что существует возможность путешествовать между любыми двумя городами, то существует в точности одно множество рейсов, которыми может воспользоваться пассажир для перемещения между двумя городами (считая что Вы воспользуетесь только одной авиалинией).

В последнее время в NCPC Авиалиниях многие часто летающие пассажиры жаловались, что им приходится слишком часто менять рейсы, чтобы добраться до конечного пункта назначения. Поскольку NCPC Авиалинии не хотят потерять своих клиентов, и при этом сохранить удобство своих рейсов, они решили отменить один из своих рейсов и заменить его другим. Помогите авиакомпании написать программу, которая поможет найти рейс, который следует отменить, а также новый рейс, который следует добавить, чтобы максимальное количество смены рейсов пассажиром при путешествии между парами городов, которые обслуживают NCPC Авиалинии, было минимальным.

Входные данные будут таковыми, что всегда можно улучшить максимальное число смены рейсов.

Входные данные

Первая строка содержит количество городов n (4 ≤ n ≤ 2500) в авиалиниях NCPC. Следующие n - 1 строка описывает рейсы. Каждый рейс задается парой городов a и b (1 ≤ a, b ≤ n).

Выходные данные

Вывести следует три строки. Первая строка содержит наименьшее количество рейсов, которое следует сменить при путешествии между парами городов после изменения одного из рейсов. Вторая строка содержит номера городов отменяемого рейса. Третья строка содержит номера городов, между которыми будет добавлен новый рейс.

Если существует несколько решений, вывести любое.