P5884 [IOI 2014] game

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

- 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 $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.

**Subtasks and Constraints** | Subtask | Score | $n$ | | :----------: | :----------: | :----------: | | $1$ | $15$ | $n=4$ | | $2$ | $27$ | $4 \le n \le 80$ | | $3$ | $58$ | $4 \le n \le 1500$ | Translated by ChatGPT 5