Молочна фабрика#10317

Молочна фабрика

1 секунда

128 мегабайтів

Дуже легка

Молочний бізнес процвітає! Завод з переробки молока фермера Джона складається з $n$ обробних станцій, пронумерованих $1, \dots, n$ 1, \ldots, n, і $n - 1$ n - 1 пішохідних переходів, кожен з яких з'єднує дві станції (переходи дорогі, тому фермер Джон хоче використати мінімальну кількість переходів, щоб можна було дістатися до будь-якої станції, починаючи з будь-якої іншої).

Щоб підвищити ефективність, фермер Джон встановив конвеєрну стрічку на кожному переході. На жаль, він надто пізно зрозумів, що кожна конвеєрна стрічка рухається лише в один бік, тому тепер рух кожною доріжкою можливий лише в одному напрямку! Тепер вже не можна потрапити з будь-якої станції до будь-якої іншої.

Однак фермер Джон вважає, що не все втрачено, якщо є хоча б одна така станція $i$ , до якої можна дістатися з кожної іншої станції. Зверніть увагу, що поїздка до станції $i$ з іншої довільної станції $j$ може включати проїзд через проміжні станції між $j$ і $i$ . Допоможіть фермеру Джону з'ясувати, чи існує така станція $i$ .

Вхідні дані

У першому рядку записано ціле число $n$ $(1 \leq n \leq 100)$ (1 \le n \le 100) — кількість обробних станцій. Кожен з наступних $n - 1$ n - 1 рядків містить два цілих числа $a_{i}$ a_i і $b_{i}$ b_i ( $1 \leq a_{i}, b_{i} \leq n$ 1 \le a_i, b_i \le n, $a_{i} \neq = b_{i}$ a_i \ne b_i). Це означає, що існує конвеєрна стрічка, яка рухається від станції $a_{i}$ a_i до станції $b_{i}$ b_i, дозволяючи пересуватися лише у напрямку від $a_{i}$ a_i до $b_{i}$ b_i.

Вихідні дані

Якщо існує станція $i$ така, що можна дійти до станції $i$ з будь-якої іншої станції, виведіть мінімальне значення $i$ . В іншому випадку виведіть $- 1$ .

Приклади

Приклад 1