Гра

Маленькому хлопчику Джан-Джи подобається грати. Коли йому ставлять запитання, він замість простої відповіді пропонує зіграти в гру.

Джан-Джи зустрів свою подружку Мей-Ю і розповів їй про мережу авіарейсів у Тайвані. У Тайвані є $n$ міст, пронумерованих від $0$ до n - 1. Між деякими містами існують авіарейси, які діють в обидва напрямки.

Мей-Ю запитала у Джан-Джи, чи можливо дістатися з будь-якого міста в будь-яке інше, використовуючи тільки авіарейси. Джан-Джи, замість відповіді, запропонував зіграти в гру.

Мей-Ю може ставити запитання типу: "Чи з'єднані міста $x$ і $y$ авіарейсом напряму?". Джан-Джи повинен одразу відповідати на кожне з цих запитань. Мей-Ю запитує про кожну пару міст рівно один раз, тобто, ставить всього r = n \cdot (n - 1) / 2 запитань. Вважається, що Мей-Ю виграє в грі, якщо після отримання відповідей на перші $i$ запитань для деякого i < r, вона може визначити, чи є мережа авіарейсів зв'язною. Це означає, що можливо дістатися з будь-якого міста в будь-яке інше, використовуючи тільки авіарейси. Якщо їй знадобилося поставити всі $r$ запитань, то виграє Джан-Джи.

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

Приклад

Розглянемо правила гри на трьох прикладах. Кожен приклад містить n = 4 міст і r = 6 раундів запитань і відповідей.

У першому прикладі (таблиця нижче) Джан-Джи програє, тому що після $4$-го запитання, Мей-Ю впевнена, що між будь-якими двома містами можна долетіти, використовуючи тільки авіарейси, незалежно від того, якими будуть відповіді на запитання $5$ і $6$.

У наступному прикладі Мей-Ю після третього запитання може визначити, що, як би Джан-Джи не відповідав далі на інші запитання, не можна дістатися з міста $0$ в місто $1$, використовуючи тільки авіарейси. У цьому випадку Джан-Джи програє знову.

У останньому прикладі Мей-Ю не може визначити відповідь на запитання доти, поки не отримає відповіді на всі $6$ запитань, тому Джан-Джи виграє. Зокрема, оскільки Джан-Джи відповів "так" на останнє запитання, то долетіти з будь-якого міста в будь-яке інше можливо. Якби він відповів "ні", то долетіти не можна.

Постановка задачі

Напишіть програму, яка допоможе Джан-Джи перемогти в грі. Зверніть увагу, що Мей-Ю і Джан-Джи не знають стратегію один одного. Мей-Ю може запитувати про пари міст у будь-якому порядку, і Джан-Джи повинен відповідати на кожне запитання одразу, не чекаючи інших запитань. Ви повинні реалізувати наступні дві функції:

• initialize($n$) - ця функція буде викликана на початку. Параметр $n$ задає число міст;

• hasEdge($u$, $v$) - ця функція буде викликана r = n \cdot (n - 1) / 2 рази. Кожен виклик цієї функції - це чергове запитання Мей-Ю. Ви повинні вибрати відповідь: чи існує прямий авіарейс між містами $u$ і $v$. Зокрема, повернене значення повинно дорівнювати $1$, якщо прямий авіарейс є, і $0$ в іншому випадку.

Оцінювання

Кожна підзадача складається з декількох ігор. Ви отримаєте бали за підзадачу тільки в разі, якщо Ви виграєте всі ігри.

Деталі реалізації

Ви повинні реалізувати функції, описані вище, використовуючи наступну сигнатуру:

C/C++ програми

• void initialize(int n);

• int hasEdge(int u, int v);

Pascal програми

• procedure initialize(n: longint);

• function hasEdge(u, v: longint): longint;