题目描述

健佳是一个喜欢做游戏的小男生。当有人问问题时，他更喜欢通过玩游戏的方式作答，而不是直接回答。健佳碰到了他的朋友梅玉，跟她讲了台湾的航空网。在台湾有 $n$ 个城市（编号为 $0,\cdots,n−1$），其中有些城市之间有航线。每个航线连接两个城市，并且是双向的。

梅玉问健佳，是否任意两个城市之间都可以坐飞机互达（直接或间接），健佳不想直接回答，而是要通过做游戏的方式来告诉她。梅玉可以问"城市 $u$ 和 $v$ 之间有直接航线吗？"，健佳会立刻直接回答该问题。梅玉会询问每对城市恰好一次，因此总计会有 $r = \frac{n (n−1)}{2}$ 个问题。如果由前 $i$（$i<r$）个问题的答案可以推断出整个航空网是否连通，也就是说，是否任意一对城市之间都可以坐飞机互达（直接或间接），梅玉就获胜。否则意味着她需要知道全部 $r$ 个回答，此时健佳获胜。

为了让游戏更好玩，他们俩同意，健佳可以不要管台湾的真实航空网，而是可以随着游戏的进展而编造航空网，也就是根据梅玉此前的提问来决定此后如何作答。你的任务是，通过决定健佳如何回答，来帮助他赢得游戏。

输入格式

• 第 $1$ 行：一个正整数 $n$，代表城市数量。
• 余下 $r$ 行：每行包含两个整数 $u$ 和 $v$，表示对城市 $u$ 和 $v$ 的提问。

输出格式

• 共 $r$ 行，对于每次梅玉的提问，你必须回答在城市 $v$ 和 $u$ 之间是否有直接航线。具体而言，返回值 $1$ 表示有，$0$ 表示没有。

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

0
1
0
1
0
1

提示

子任务及数据规模