分析

首先想到的一个优化就是考虑去掉一些没用的点。怎么做呢？

我们可以把满足：

• $x,y$ 在所有点中出现次数 $\le 2$。
• $(x,y)$ 没有访问过。

这些条件的点存储起来，构造集合 $S$，查询时只需要找这些点。

证明

现在我们要证明：若 $|S|\ge 5$，对于任意一个 $t(x,y)$，$S$ 中存在 $p(x_p,y_p)$，满足 $x_p≠x,y_p≠y$。

设 $A=\{q\in S|x_q=x\}$。

设 $B=\{q\in S|y_q=y\}$。

根据定义，$|A|\le 2,|B|\le 2$，所以 $|A\cup B|\le|A|+|B|\le 4<|S|$。

所以必定存在。

对于 $|S|\le 4$：

如果有解，必然 $x_p≠x,y_p≠y$，在 $S$ 中。

如果无解，必然不存在 $x_p≠x,y_p≠y$，$S$ 中不存在。

解释

解释为什么限制 $x,y$ 的出现为 $2$ 不是 $1$：

if(mx[qp.x]<=2&&my[qp.y]<=2&&!vis[qp]){
	++mx[qp.x];
	++my[qp.y];
	vis[qp]=1;
	p.emplace_back((node){qp,i});
}

这是因为可能存在 $1$ 个点是被摧毁的，且 $mx_x=1$，必须限制为 $2$，才能找到没有被摧毁的那一个点。

时间复杂度

与 $t$ 共享 $x$ 或 $y$ 坐标的点最多有 $4$ 个（$x$ 相同的最多 $2$ 个，$y$ 相同的最多 $2$ 个）。

$O(n\log n+q)$，主要是使用了 map。

//SPJ:???
// #include<bits/stdc++.h>
#include<bits/extc++.h>
#define gp __gnu_pbds::gp_hash_table
#define endl '\n'
#define hh puts("")
//#define int long long
#define uap unordered_map
#define uet unordered_set
#define sr() srand(time(NULL))
#define rando(cntmax,istart,rng) for(int i=istart,cnt=0;cnt<=cntmax;cnt++,i=(rand()%rng))
#define lrfor(l,r) for(int cnt=1,i=l,j=r,forid=i;i<j&&l<=i&&i<=r&&l<=j&&j<=r;i+=cnt%2,j-=cnt%2,forid=(cnt%2?j:i),++cnt)
#define lrfor2(l,r) for(size_t cnt=1,i=l,j=r,forid=i;i<j&&l<=i&&i<=r&&l<=j&&j<=r;i+=cnt%2,j-=cnt%2,forid=(cnt%2?j:i),++cnt)
#define IAKIOI ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,mn,stdin),p1==p2)?EOF:*p1++)
namespace IO{
	const int mn=1e6+100;
	char buf[mn],*p1=buf,*p2=buf;
	inline int read(){
		int x=0,f=1;char ch=getchar();
		while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
		while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
		return x*f;
	}
	inline void write(int x){
		if(x<0){putchar('-');x=-x;}
		if(x>9)write(x/10);
		putchar(x%10+'0');
	}
}using namespace IO;
const int N=1e6+10;
using namespace std;
struct point{
	int x,y;
	friend inline bool operator<(point aa,point bb){return(aa.x!=bb.x?aa.x<bb.x:aa.y<bb.y);}
//	friend inline bool operator==(point aa,point bb){return aa.x==bb.x&&aa.y==bb.y;}
};
struct node{
	point dot;
	int id;
};
gp<int,int> mx,my;
map<point,bool> vis;
vector<node> p;
inline bool check(point che,point man){
	return man.x!=che.x&&man.y!=che.y;
}
signed main(){
	int n,q;
	n=read();
	q=read();
	for(int i=1;i<=n;++i){
		point qp;
		qp.x=read();
		qp.y=read();
		if(mx[qp.x]<=2&&my[qp.y]<=2&&!vis[qp]){
			++mx[qp.x];
			++my[qp.y];
			vis[qp]=1;
			p.emplace_back((node){qp,i});
		}
	}
	while(q--){
		point t;
		t.x=read();
		t.y=read();
		bool flag=0;
		for(int i=1;i<p.size();i++){
			point q=p[i].dot;
			if(check(t,q)){
				write(p[i].id);
				hh;
				flag=1;
				break;
			}
		}
		if(!flag)write(-1),hh;
	}
	return 0;
}