#include <bits/stdc++.h>

#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define mod 1000000007
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back

using namespace std;

static int n, k;
static int question_num = 0;
static int h[1001][1001];


int d[3010][3010];
int x[3010],y[3010];

int Pitaj(int i, int j);

vector<int> Nadji(int N, int K) {
	vector<int>out;
	int i=1,j=1;
	memset(x,0,sizeof(x));
	memset(y,0,sizeof(y));

    for (int q=0;;q++){
        if (q%2==0){
            pair<int,int>p={i,j};
            vector<pair<int,int>>v;

            for (int k=1;k<=N;k++){
                if (k==j and i!=1 and j!=1)continue;
                d[i][k]=Pitaj(i,k);
            }
            for (int k=1;k<=N;k++)
                v.pb({d[i][k],k});
            sort(rall(v));

            int cnt=0;
            for (int k=1;k<=N;k++){
                if (d[i][k]==v[0].fi)cnt++;
            }
            if (cnt==1)x[i]=v[0].se;
            else x[i]=-1;

            if (y[v[0].se]==i and x[i]==v[0].se){
                out.pb(i),out.pb(j);
                return out;
            }

            for (auto t:v){
                if (y[t.se])continue;
                j=t.se;
                break;
            }


            //cout<<i<<" "<<j<<" "<<x[i]<<"\n";
            //if (q==2)exit(0);
        }
        else{
            pair<int,int>p={i,j};
            vector<pair<int,int>>v;

            for (int k=1;k<=N;k++){
                if (k==i)continue;
                d[k][j]=Pitaj(k,j);
            }
            for (int k=1;k<=N;k++)
                v.pb({d[k][j],k});
            sort(all(v));

            int cnt=0;
            for (int k=1;k<=N;k++){
                if (d[k][j]==v[0].fi)cnt++;
            }
            if (cnt==1)y[j]=v[0].se;
            else y[j]=-1;

            if (x[v[0].se]==j and y[j]==v[0].se){
                out.pb(i),out.pb(j);
                return out;
            }

            for (auto t:v){
                if (x[t.se])continue;
                i=t.se;
                break;
            }

            //cout<<i<<" "<<j<<" "<<y[j]<<"\n";
        }
    }

	return out;
}