Три міста#1743
В одній державі є міст. Деякі міста з'єднані дорогами, і для будь-яких двох міст і виконується така властивість: існує рівно один шлях, щоб дістатися від міста до міста , якщо можна рухатись лише дорогами і заборонено проходити одну й ту ж дорогу більше одного разу.
Нещодавно президента цієї країни зацікавило питання: які три міста розташовані найдалі одне від одного? А саме, взаємна відстань трьох міст , і визначається як мінімальна кількість доріг, яку потрібно використати, щоб дістатися від до , потім від до , а потім від до (при цьому дозволяється використовувати одну й ту ж дорогу в різних маршрутах).
Потрібно знайти такі три міста, для яких взаємна відстань між ними буде максимальною.
Наприклад, для п’яти міст, з’єднаних дорогами як на рисунку 1, три найбільш віддалені міста — це , та (взаємна відстань 2 + 3 + 3 = 8), а для міст на рисунку 2 — це будь-які три міста, вибрані з множини \{1, 2, 4, 5\} (відстань 2 + 2 + 2 = 6).
Перший рядок містить число — кількість міст (3 \leq N \leq 1000). Наступні рядків містять опис міст. Опис -го міста починається з K_i — кількості міст, з якими воно з'єднане дорогами (1 \leq K_i \leq N), далі йдуть K_i чисел — номери міст, з якими воно з’єднане.
Гарантується, що вхідні дані коректні: якщо існує дорога з міста до міста , то існує дорога й з міста до міста , і для всіх пар міст виконується зазначена у задачі властивість.
Виведіть три різні числа — номери трьох найбільш віддалених міст у будь-якому порядку. Якщо існує кілька відповідей, виведіть будь-яку з них.
Приклад 1