ABC find 4-cycle (pigeon nest theorem)

F

The question ：
It's for you. n+k Points and m side , Two points on each side, one point <=n, One point >n, There is no double edge . Now I ask if you have a size of 4 Rings , If there is any output , If no output -1.n<=3e5,k<=3000.

reflection ：
First of all, the two points on the side must be in the two point sets , Draw a picture and find , For two points in a point set . If they contain points >=2 A the same , Then you can output these four points . Find out k Very small , therefore kk The complexity of enumerates which two points , It's stuck here , How to find what they have in common ？ This cannot be done quickly . If you enumerate n This point set , Not to mention .
Actually , For the point on the left , It contains some points on the right . If these points are enumerated twice , See if any two points are elsewhere i It's OK to include this in the point ？ But a want to , Each point 3000 A little bit , Complexity nk*k, It's not going to work . But think about it , Not so many times , For example, the first point contains k/2 A little bit , The second point contains different k/2 A little bit , The third point, if it contains points >=3 Then there must be two included by others , Here is the pigeon nest theorem .
So it's just some problems that you can't do with complexity , You can try , Because when there is no other algorithm, it is usually violence , This violence looks like violence, in fact , If you add some details, you will not run so many times .

Code ：

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 4e5+10,M = 3010;

int T,n,m,k;
int va[M][M]; // If you use map<PII,int> mp To mark , Will timeout 

set<int> s[N];

signed main()
{
    
	IOS;
	cin>>n>>k>>m;
	while(m--)
	{
    
		int a,b;
		cin>>a>>b;
		s[a].insert(b-n);
	}
	for(int i=1;i<=n;i++)
	{
    
		for(auto t1:s[i])
		{
    
			for(auto t2:s[i])
			{
    
				if(t1==t2) continue;
				int a = t1,b = t2;
				if(!va[a][b]) va[a][b] = i;
				else
				{
    
					cout<<a+n<<" "<<b+n<<" "<<va[a][b]<<" "<<i;
					return 0;
				}
			}
		}
	}
	cout<<-1;
	return 0;
}

summary ：
Try more , Think more .