健佳是一个喜欢做游戏的小男生。当有人问问题时，他更喜欢通过玩游戏的方式作答，而不是直接回答。健佳碰到了他的朋友梅玉，跟她讲了台湾的航空网。在台湾有 $n$ 个城市 (编号为 $0, \cdots, n - 1$)，其中有些城市之间有航线。每个航线连接两个城市，并且是双向的。
梅玉问健佳，是否任意两个城市之间都可以坐飞机互达 (直接或间接)，健佳不想直接回答，而是要通过做游戏的方式来告诉她。梅玉可以问 "城市 $u$ 和 $v$ 之间有直接航线吗？"，健佳会立刻直接回答该问题。梅玉会询问每对城市恰好一次，因此总计会有 $r = \dbinom n2$ 个问题。
如果由前 $i$ ($i < r$) 个问题的答案可以推断出整个航空网是否连通，也就是说，是否任意一对城市之间都可以坐飞机互达 (直接或间接)，梅玉就获胜。否则意味着她需要知道全部 $r$ 个回答，此时健佳获胜。
为了让游戏更好玩，他们俩同意，健佳可以不要管台湾的真实航空网，而是可以随着游戏的进展而编造航空网，也就是根据梅玉此前的提问来决定此后如何作答。你的任务是，通过决定健佳如何回答，来帮助他赢得游戏。
请写出一个可以帮助健佳获胜的程序。注意，无论是梅玉还是健佳，都不知道对方的策略。梅玉可以以任意的顺序来询问城市对，而健佳必须在不清楚后面提问的前提下立刻给出回答。你需要实现下面的两个函数：
本题只支持 C/C++。
你只能提交一个源文件实现上述的函数，其命名与接口需遵循下面的要求。你还要在该文件中包含头文件 game.h。
void initialize(int n);
int hasEdge(int u, int v);
题目意思即，当她知道前 $r-1$ 个回答后，仍无法确定判断图的连通性。这意味着最后一个 (第 $r$ 个) 回答的真假 ($u_r, v_r$ 是否有边相连) 决定了整个图是否连通。那么肯定是当 $u_r, v_r$ 有边时连通，无边不连通，即 $(u_r, v_r)$ 是一个桥边。
由于最后一个回答对整个方案已经没有实质性的影响，因此我们总是假定最后一个问题的答案是真 (有边相连)，即整张图是一个连通图，且 $(u_r, v_r)$ 是桥边。
怎么才能保证它是桥边呢？我们尝试着让桥边尽可能的多。什么图具有最多的桥边？仙人掌？当然是树啦。因此我们希望造出的图是一棵树。
由于树的边数只有 $n-1$，因此大多数问题的回答都是假，只有少量问题为真。(注意以下分析中点的编号为 $1 \sim n$)
随便取一个点 $n$，对它进行分析。梅玉会问 $n-1$ 个与点 $n$ 有关的信息。(显然不能都回答假，不然就不是树了) 我们可以选择在前 $n-2$ 次回答假，再最后一次回答真。那么，她只有再问完所有与 $n$ 有关的的问题后，才能确定点 $n$ 与其它点的连通性。
如果关于 $n$ 的最后一次询问就是第 $r$ 次，那么就成功构造了。否则的话，我们可以将点 $n$ 从原图中去除，且不影响答案 (因为在前 $r-1$ 次就知道点 $n$ 与其它点是连通的，因此可以不用考虑)。于是原题就转化为了点数为 $n-1$ 的子问题。对 $n-1$ 同样进行上述操作 (对梅玉问的 $n-2$ 个问题，只有最后一次回答真)，依次类推……
一直到 $n=2$ 时，最后只有一条边，这条边的真假就能确定图的连通性了。且容易证明，造出的图一定是一棵树。
综上所述，总的策略就是：对于每对询问 $(u, v)$ (其中 $u < v$，否则交换过来)，如果这是关于点 $v$ 的第 $v-1$ 次询问 (即最后一次询问)，就回答真，否则回答假。
时间复杂度：预处理 $O(0)$，单次询问 $O(1)$，代码极易实现。
#include "game.h"
#include <utility>
#define N 1600
int deg[N];
void initialize(int n) {}
int hasEdge(int u, int v){
if(u > v) std::swap(u, v);
return ++deg[v] == v;
}
坑1："game.h" 头文件注意是引号，交换变量的时候注意 #include <utility> (或者 <algorithm>)。