Description

Jianjia is a boy who likes playing games. When someone asks him a question, he prefers to answer by playing a game instead of answering directly. Jianjia met his friend Meiyu and told her about Taiwan’s airline network. In Taiwan there are $n$ cities (numbered $0,\cdots,n−1$), and there are air routes between some pairs of cities. Each route connects two cities and is bidirectional.

Meiyu asked Jianjia whether it is possible to travel by plane between any two cities (directly or indirectly). Jianjia does not want to answer directly, and instead wants to tell her through a game. Meiyu may ask, “Is there a direct air route between cities $u$ and $v$?”, and Jianjia must answer immediately. Meiyu will ask about each pair of cities exactly once, so in total there will be $r = \frac{n (n−1)}{2}$ questions. If from the answers to the first $i$ questions ($i<r$) it is already possible to determine whether the whole airline network is connected, that is, whether it is possible to travel between any pair of cities by plane (directly or indirectly), then Meiyu wins. Otherwise, this means she needs to know all $r$ answers, and then Jianjia wins.

To make the game more fun, they agreed that Jianjia does not have to follow the real airline network in Taiwan. Instead, he may make up the airline network as the game progresses, that is, he can decide how to answer later based on Meiyu’s previous questions. Your task is to help him win the game by deciding how Jianjia should answer.

Input Format

• Line $1$: A positive integer $n$, the number of cities.
• The remaining $r$ lines: Each line contains two integers $u$ and $v$, representing a question about cities $u$ and $v$.

Output Format

• Output $r$ lines. For each question from Meiyu, you must answer whether there is a direct air route between cities $v$ and $u$. Specifically, output $1$ if there is, and $0$ if there is not.

4
0 3
1 0
0 2
3 1
1 2
2 3

0
1
0
1
0
1

Hint

Subtasks and Constraints

Translated by ChatGPT 5