题目描述

Y 国是一个由 $n$ 个城市组成的国家。每两个城市都有且仅有一条单向道路相连。即如果将 Y 国的每一个城市抽象为一个点，将每一条道路抽象为一条边，最终的图是一个竞赛图。小 L 想找一个城市定居。他希望定居的城市的出度尽可能大，这样他可以更方便地从那个城市到其他城市。

小 L 给出了他希望定居的城市一个形式化的定义：一个城市称之为“好的”，当且仅当它的出度 $\geq n-2$。小 $L$ 只会在好的城市定居。但是小 $L$ 并不知道每条边的具体方向，但是他可以花 $1$ 单位的时间调查某一条边的方向。现在，小 $L$ 想请您帮忙，他希望您可以在 $q$ 单位的时间内指挥小 $L$ 调查某些边的方向，并找到一个好的城市，或者报告不存在好的城市。如果有多个好的城市，输出任意一个即可。

交互方式

在你的程序开头，需要引用库city.h。

你的程序不需要，也不应该实现main函数。只需要实现一个函数：

int solve(int n)

其中，$n$ 表示城市的点的个数。该函数的返回值是你找到的好的城市的编号，如果不存在好的城市，则返回 $-1$。

你的程序将会被调用多次 $solve$ 函数，请在每次调用前注意清空数组。

你的程序可以调用函数：

bool ask(int x,int y)

表示询问 $x$ 和 $y$ 之间的边的方向，如果方向是从 $x$ 指向 $y$ 则返回值是 $1$，否则返回值是 $0$。你需要保证 $1 \leq x,y \leq n,x \neq y$。

样例1

$n=4$，边的顺序分别为 $ 1 \rightarrow 2~,~3 \rightarrow 1~,~ 2 \rightarrow 3~,~ 1 \rightarrow 4 ~,~ 4 \rightarrow 2 ~,~ 4 \rightarrow 3 $。

调用 $ask(1,2)$ ，返回 $1$。

调用 $ask(1,3)$ ，返回 $0$。

调用 $ask(1,4)$ ，返回 $1$。

找到 $1$ 是一个好的城市，返回 $1$ 即可。

限制与约定

$subtask 1(10pts)：n \leq 100，\sum n \leq 1000，q= \frac {n*(n-1)} {2}$。

$subtask 2(20pts)：n \leq 100，\sum n \leq 10^6，q = 10n$。

$subtask 3(30pts)：n \leq 1000，\sum n \leq 10^6，q = 5n$。

$subtask 4(40pts)：n \leq 1000，\sum n \leq 10^6，q = 4n$。

对于所有数据，满足 $3 \leq n \leq 1000，\sum n^2 \leq 10^7$。

保证交互库运行所需的时间不超过 1s，空间不超过 128M。