#include<bits/stdc++.h>
#define maxn 1005

int a[maxn][maxn];
int maxred[maxn],brmax[maxn];
int minkol[maxn],brmin[maxn];
std::vector<int>res;
bool moze[maxn][maxn];
std::vector<int> Nadji(int n, int k)
{
	if(k>=n*n)
	{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)a[i][j]=Pitaj(i,j);

		for(int i=1;i<=n;i++)
		{
			maxred[i]=1;
			brmax[i]=1;

			for(int j=2;j<=n;j++)
			{
				if(a[i][maxred[i]]==a[i][j])brmax[i]++;
				if(a[i][j]>a[i][maxred[i]])
				{
					maxred[i]=j;
					brmax[i]=1;
				}
			}

			//cout<<i<<","<<maxred[i]<<","<<brmax[i]<<endl;
		}

		for(int j=1;j<=n;j++)
		{
			minkol[j]=1;
			brmin[j]=1;

			for(int i=2;i<=n;i++)
			{
				if(a[minkol[j]][j]==a[i][j])brmin[j]++;
				if(a[i][j]<a[minkol[j]][j])
				{
					minkol[j]=i;
					brmin[j]=1;
				}
			}

			//cout<<j<<","<<minkol[j]<<","<<brmin[j]<<endl;
		}

		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				if(brmax[i]==1 && brmin[j]==1 && minkol[j]==i && maxred[i]==j)
				{
					res.push_back(i);
					res.push_back(j);
					return res;
				}
			}
	}

	/*else if(n==1000 && k==5000)
	{
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)moze[i][j]=true;
		for(int i=
	}*/

	else if(n==1000 && k==501500)
	{
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)moze[i][j]=true;
		for(int i=1;i<=n;i++)
		{
			a[i][i]=Pitaj(i,i);
			maxred[i]=i;
			brmax[i]=1;
			brmin[i]=1;
			minkol[i]=i;
		}
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
			{
				if(a[i][i]==a[j][j])
				{
					moze[i][j]=false;
					moze[j][i]=false;
				}
				else if(a[i][i]>a[j][j])
				{
					moze[i][j]=false;
				}
				else
				{
					moze[j][i]=false;
				}
			}

		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(a[minkol[j]][j]<=a[i][maxred[i]])moze[i][j]=false;
				if(moze[i][j] && !a[i][j])
				{
					a[i][j]=Pitaj(i,j);
					if(a[i][j]>a[i][maxred[i]])
					{
						maxred[i]=j;
						brmax[i]=1;
					}
					if(a[i][j]==a[i][maxred[i]])brmax[i]++;
					if(a[i][j]<a[minkol[j]][j])
					{
						minkol[j]=i;
						brmin[j]=1;
					}
				}
			}
		}

		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				if(brmax[i]==1 && brmin[j]==1 && minkol[j]==i && maxred[i]==j)
				{
					res.push_back(i);
					res.push_back(j);
					return res;
				}
			}
	}

	res.push_back(0);
	res.push_back(0);
	return res;
}