Гра
Маленькому хлопчику Джан-Джи подобається грати. Коли йому ставлять запитання, він замість простої відповіді пропонує зіграти в гру.
Джан-Джи зустрів свою подружку Мей-Ю і розповів їй про мережу авіарейсів у Тайвані. У Тайвані є n міст, пронумерованих від 0 до n - 1. Між деякими містами існують авіарейси, які діють в обидва напрямки.
Мей-Ю запитала у Джан-Джи, чи можливо дістатися з будь-якого міста в будь-яке інше, використовуючи тільки авіарейси. Джан-Джи, замість відповіді, запропонував зіграти в гру.
Мей-Ю може ставити запитання типу: "Чи з'єднані міста x і y авіарейсом напряму?". Джан-Джи повинен одразу відповідати на кожне з цих запитань. Мей-Ю запитує про кожну пару міст рівно один раз, тобто, ставить всього r = n * (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 * (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;
Вхідні дані
Грейдер читає вхід у наступному форматі:
перший рядок містить число n;
кожен з наступних r рядків містить два цілих числа u і v, що описують запит про міста u і v.
Вихідні дані
Для кожного запитання в окремому рядку буде надруковано 1, якщо існує ребро між u і v, і 0 в іншому випадку.