P5884 [IOI 2014] game 游戏

健佳是一个喜欢做游戏的小男生。当有人问问题时，他更喜欢通过玩游戏的方式作答，而不是直接回答。健佳碰到了他的朋友梅玉，跟她讲了台湾的航空网。在台湾有 $n$ 个城市（编号为 $0,\cdots,n−1$），其中有些城市之间有航线。每个航线连接两个城市，并且是双向的。 梅玉问健佳，是否任意两个城市之间都可以坐飞机互达（直接或间接），健佳不想直接回答，而是要通过做游戏的方式来告诉她。梅玉可以问"城市 $u$ 和 $v$ 之间有直接航线吗？"，健佳会立刻直接回答该问题。梅玉会询问每对城市恰好一次，因此总计会有 $r = \frac{n (n−1)}{2}$ 个问题。如果由前 $i$（$i

无

无

**子任务及数据规模** | 子任务 | 分值 | $n$ | | :----------: | :----------: | :----------: | | $1$ | $15$ | $n=4$ | | $2$ | $27$ | $4 \le n \le 80$ | | $3$ | $58$ | $4 \le n \le 1500$ |