注意到你可以选择报告无解。

考虑猜测一些比较复杂的图形态是无解的，比如说存在环的图，证明很简单：翻转环上所有边的方向之后不会改变任意询问的结果。

于是考虑 topo 排序，假设你已经将 $S$ 中的点加入过队列了，现在你要判断点 $x$ 是否只有来自 $S$ 中的入边，考虑将 $S$ 中的点全部设置为 $0$，将 $U \backslash (S \cup \{x\})$ 中的点全部设置为 $1$，然后比较将 $x$ 设置为 $0$ 和 $1$ 的答案是否相同即可。

找出一个 $0$ 入度点 $x$ 之后考虑确定它连出去的边，对于没有被加入过队列的点集做分治即可（对于一个集合 $S$ 和一个点 $x$ 容易判断是否存在 $x$ 连向 $S$ 内任意一点的边）。

我一开始实现的时候忘记了怎么 topo 排序，用线段树维护了 $\min deg$，但是事实上 topo 排序告诉我们增量的考虑是否有新的点可能成为 $0$ 入度的点就行。

总操作次数是 $O(m \log n)$ 的，可以通过。

#include "voltage.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 514;
int tr[maxn<<2];
vector<int> vis;
int n;
void pushup(int cur){
	//比较度数（vis[i]=1）的点被删除
	if(tr[cur<<1]==-1) tr[cur]=tr[cur<<1|1];
	else if(tr[cur<<1|1]==-1) tr[cur]=tr[cur<<1];
	else{
		vector<int> x(n),y(n);
		for(int i=0;i<n;i++){
			if(vis[i]==1) x[i]=y[i]=0;
			else x[i]=y[i]=1;
		}
		x[tr[cur<<1]]=0;
		y[tr[cur<<1|1]]=0;
		int res=query(x,y);
		if(res==-1) tr[cur]=tr[cur<<1|1];
		else tr[cur]=tr[cur<<1];
	}
}
void build(int cur,int lt,int rt){
	if(lt==rt){
		tr[cur]=lt;
		return ;
	}
	int mid=(lt+rt)>>1;
	build(cur<<1,lt,mid);
	build(cur<<1|1,mid+1,rt);
	pushup(cur);
}
void upd(int cur,int lt,int rt,int pos,int c){
	if(lt==rt){
		tr[cur]=c;
		return ;
	}
	int mid=(lt+rt)>>1;
	if(pos<=mid) upd(cur<<1,lt,mid,pos,c);
	else upd(cur<<1|1,mid+1,rt,pos,c);
	pushup(cur);
}
vector< pair<int,int> > ans;
void conv(int u,vector<int> P){
	//如果 P 中完全没有 u 的出边则返回
	vector<int> x(n),y(n);
	for(int i=0;i<n;i++){
		if(vis[i]==1) x[i]=y[i]=0;
		else x[i]=y[i]=1;
	}
	for(int v:P) x[v]=y[v]=0;
	x[u]=1;
	if(query(x,y)==0) return ;
	if(P.size()==1){
		int v=P.back();
		//v 的度数发生变化，在线段树上更新 v
		ans.push_back({u,v});
		upd(1,0,n-1,v,v);
		return ;
	}
	vector<int> L,R;
	for(int i=0;i<P.size()/2;i++) L.push_back(P[i]);
	for(int i=P.size()/2;i<P.size();i++) R.push_back(P[i]);
	conv(u,L),conv(u,R);
}
bool solve(int N,int M){
	n=N;
	vis.resize(n);
	for(int i=0;i<n;i++){
		vis[i]=0;
	}
	build(1,0,n-1);
	for(int i=0;i<n;i++){
		//vis[i]=1 的点是已经加入队列的点
		int u=tr[1];
		//确保 u 真的是 0 入度点
		vector<int> x(n),y(n);
		for(int j=0;j<n;j++){
			if(vis[j]==1) x[j]=y[j]=0;
			else x[j]=y[j]=1;
		}		
		x[u]=0;
		if(query(x,y)!=0) return false;
		vis[u]=1;
		upd(1,0,n-1,u,-1);
		//找到 u 的出边
		vector<int> P;
		for(int j=0;j<n;j++){
			if(vis[j]==0) P.push_back(j);
		}
		conv(u,P);
	}
	for(pair<int,int> now:ans) answer(now.first,now.second);
	return true;
}