简要题意：

这是一道交互题。

有一个大小为 $n$ 的竞赛图，每次可以询问一条边的方向。

希望找到一个出度不小于 $n-2$ 的点，求出任意一个这样的点或者报告不存在这样的点。

$n\le 1000$，询问次数不超过 $4n$，多测，$\sum n^2\le {10}^7$。

首先出度不小于 $n-2$ 等价于入度小于等于 $1$。

考虑对于一个已经确定内部形态的，可能的集合 $S$，初始时 $S$ 为空，根据 $S$ 来排除不可能的点，具体的：

• 枚举一个 $u$，将 $u$ 加入 $S$ 中；
• 求出 $S$ 内的所有边并删除不可能的点。

因为若确定内部形态的点并且全都可能的集合大小为 $3$，则此集合只有三元环一种可能，并且不存在某一个合法集合大小为 $4$，因为此时有一个点不合法。

故最后可能的集合为 $S$，$S$ 大小至多为 $3$，需要暴力枚举每一个 $S$ 内的元素暴力 check。

第一步最多是 $3n$，第二步也最多是 $3n$，故询问次数是 $6n$，不能通过。

注意到实际上对于大部分情况下第一步删除一个点的步数是小于 $3$ 步，但仍然存在情况会卡满，故尝试随机顺序加入集合，对于第二步的暴力 check 也可以随机顺序进行 check。

经过本机的测试，可以通过。

下面其实是求助，因为我并不会证明平均次数在 $4n$ 内，希望有大佬可以证明一下这个做法的平均次数是 $4n$ 以内或者可以叉掉这个做法。

附我的代码：

// Author: cnyz
#include "city.h"
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pb emplace_back
using namespace std;
const int N=1005;
mt19937 rng(time(0));
vector<int> pos[N];
int deg[N],p[N];
int vis[N][N];
set<int> now;
int nn;
bool Ask(int x,int y) {
    bool F=vis[x][y]!=-1?vis[x][y]:ask(x,y);
    vis[x][y]=F,vis[y][x]=F^1;
    return F;
}
void qry(int x,int y) {
    bool fl=Ask(x,y);
    if(fl) deg[y]++,pos[x].pb(y);
    else deg[x]++,pos[y].pb(x);
}
bool chk(int u) {
    int tmp=0;
    shuffle(p+1,p+nn+1,rng);
    FOR(i,1,nn) if(u!=p[i]) {
        tmp+=Ask(p[i],u);
        if(tmp>=2) return 0;
    }
    return 1;
}
int solve(int n) {
    nn=n;
    FOR(i,1,n) deg[i]=0,pos[i].clear(),p[i]=i;
    FOR(i,1,n) FOR(j,1,n) vis[i][j]=-1;
    shuffle(p+1,p+n+1,rng);
    now.clear(),now.insert(p[1]);
    FOR(i,2,n) {
        for(int j:now) qry(p[i],j);
        now.insert(p[i]);
        vector<int> tmp;tmp.clear();
        for(int j:now) if(deg[j]>=2) tmp.pb(j);
        for(int j:tmp) now.erase(j);
    }
    vector<int> tmp;tmp.clear();
    for(int u:now) tmp.pb(u);
    shuffle(tmp.begin(),tmp.end(),rng);
    for(int u:tmp) if(chk(u)) return u;
    return -1; 
}