Маленькому мальчику Джан-Джи нравится играть. Когда ему задают вопрос, вместо простого ответа он предлагает сыграть в игру.

Джан-Джи встретил свою подружку Мей-Ю и рассказал ей о том, как устроена сеть авиарейсов в Тайване. В частности, в Тайване есть 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 в противном случае.