#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <vector>
#include <ctime>
#include <cassert>
#include <algorithm>
#include <cmath>

#pragma comment(linker,"/STACK:20000000")

using namespace std;

const int FIRST_GENERATED_TEST = 2;
const int MAXN = 100000;

string itos(int n){
	stringstream ss; ss << n;
	return ss.str();
}

int random(int a){
	return rand()%a;
}

int random(int a, int b){
	return random(b-a+1)+a;
}

int test_num = 2;

void next_test(){
	freopen((itos(test_num++)+".in").c_str(),"w",stdout);
}

vector<int> mate[MAXN+1];
vector<pair<int,int> >edges;

void make_random_test(int n, int m, bool loops_allowed=false){
	assert(m >= 2*n && m <= 3*n);
	
	next_test();
	printf("%d %d\n",n,m);
	edges.clear();
	for (int i=2; i<=n; ++i) {
		int p = (rand()%(i-1))+1;
		printf("%d %d\n",p,i);
	}
	for (int i=n; i<=m; ++i) {
		int a = (rand()%n)+1;
		int b = (rand()%n)+1;
		if (!loops_allowed) while (a==b) {
			assert(n > 1);
			a = (rand()%n)+1;
			b = (rand()%n)+1;
		}
		printf("%d %d\n",a,b);
	}
}

void make_random_test(int n, bool loops_allowed=false){
	make_random_test(n,(rand()%(n+1))+2*n, loops_allowed);
}

void make_random_test(bool loops_allowed=false){
	make_random_test((rand()%MAXN)+1,loops_allowed);
}

void make_special_test_1(int n=MAXN){
	// fork
	assert(n >= 4);
	next_test();
	printf("%d %d\n",n,2*n);
	vector<pair<int,int> > e;
	vector<int> p(n);
	for (int i=0; i<n; ++i) p[i]=i+1;
	random_shuffle(p.begin(),p.end());
	
	for (int i=0; i<n-2; ++i) e.push_back(make_pair(p[i],p[i+1])),e.push_back(make_pair(p[i],p[i+1]));
	e.push_back(make_pair(p[0],p[n-1]));
	e.push_back(make_pair(p[0],p[n-2]));
	e.push_back(make_pair(p[n-3],p[n-2]));
	e.push_back(make_pair(p[n-3],p[n-1]));
	e.push_back(make_pair(p[n-3],p[n-2]));
	e.push_back(make_pair(p[n-3],p[n-1]));
	
	random_shuffle(e.begin(),e.end());
	
	for (int i=0; i<2*n; ++i) printf("%d %d\n",e[i].first,e[i].second);
}

void make_special_test_2(int n=MAXN){
	// fork
	assert(n >= 4);
	next_test();
	printf("%d %d\n",n,2*n);
	vector<pair<int,int> > e;
	vector<int> p(n);
	for (int i=0; i<n; ++i) p[i]=i+1;
	random_shuffle(p.begin(),p.end());
	
	for (int i=0; i<n-2; ++i) e.push_back(make_pair(p[i],p[i+1])),e.push_back(make_pair(p[i],p[i+1]));
	e.push_back(make_pair(p[0],p[n-1]));
	e.push_back(make_pair(p[0],p[n/2]));
	e.push_back(make_pair(p[n-3],p[n-2]));
	e.push_back(make_pair(p[n-3],p[n-1]));
	e.push_back(make_pair(p[n-3],p[n-2]));
	e.push_back(make_pair(p[n-3],p[n-1]));
	
	random_shuffle(e.begin(),e.end());
	
	for (int i=0; i<2*n; ++i) printf("%d %d\n",e[i].first,e[i].second);
}

void make_special_test_3(int n, int k){
	assert(n >= 20);
	next_test();
	
	vector<pair<int,int> > e;
	vector<int> p(n);
	for (int i=0; i<n; ++i) p[i]=i+1;
	random_shuffle(p.begin(),p.end());
	
	for (int i=0; i<k; ++i)
		for (int j=i+1; j<k; ++j) e.push_back(make_pair(p[i],p[j])), e.push_back(make_pair(p[n-i-1],p[n-j-1]));
	
	for (int i=k-1; i<n-k; ++i) e.push_back(make_pair(p[i],p[i+1])), e.push_back(make_pair(p[i+1],p[i])); 
	
	random_shuffle(e.begin(),e.end());
	printf("%d %d\n",n,e.size());
	for (int i=0; i<(int)e.size(); ++i) printf("%d %d\n",e[i].first,e[i].second);
}

void make_special_test_3(int n = MAXN){
	make_special_test_3(n,random(5,(int)( (sqrt(4*n+17.0)+5)/2 )));
}

void make_special_test_4(){
	next_test();
	
	printf("%d %d\n",100000,200000);
	vector<pair<int,int> > e;
	vector<int> p(100000);
	for (int i=0; i<100000; ++i) p[i]=i+1;
	random_shuffle(p.begin(),p.end());
	
	for (int i=0; i<100000; i+=100){
		for (int j=0; j<99; ++j) e.push_back(make_pair(p[i+j],p[i+j+1])),e.push_back(make_pair(p[i+j+1],p[i+j]));
		if (i+100 < 100000) {
			e.push_back(make_pair(p[i+100],p[i])),e.push_back(make_pair(p[i],p[i+100]));
		}
	}
	
	e.push_back(make_pair(p[5678],p[5631]));
	
	e.push_back(make_pair(p[7678],p[7631]));
	
	random_shuffle(e.begin(),e.end());
	for (int i=0; i<(int)e.size(); ++i) printf("%d %d\n",e[i].first,e[i].second);
}

void make_special_test_5(){
	next_test();
	
	printf("%d %d\n",100000,200000);
	vector<pair<int,int> > e;
	vector<int> p(100000);
	for (int i=0; i<100000; ++i) p[i]=i+1;
	random_shuffle(p.begin(),p.end());
	
	for (int i=0; i<100000; i+=100){
		for (int j=0; j<99; ++j) e.push_back(make_pair(p[i+j],p[i+j+1])),e.push_back(make_pair(p[i+j+1],p[i+j]));
		if (i+100 < 100000) {
			e.push_back(make_pair(p[i+100],p[i])),e.push_back(make_pair(p[i],p[i+100]));
		}
	}
	
	e.push_back(make_pair(p[5678],p[5680]));
	
	e.push_back(make_pair(p[7678],p[7680]));
	
	random_shuffle(e.begin(),e.end());
	for (int i=0; i<(int)e.size(); ++i) printf("%d %d\n",e[i].first,e[i].second);
}

void make_special_test_6(){
	next_test();
	
	printf("%d %d\n",100000,200000);
	vector<pair<int,int> > e;
	vector<int> p(100000);
	for (int i=0; i<100000; ++i) p[i]=i+1;
	random_shuffle(p.begin(),p.end());
	
	for (int i=0; i<100000; i+=100){
		for (int j=0; j<99; ++j) e.push_back(make_pair(p[i+j],p[i+j+1])),e.push_back(make_pair(p[i+j+1],p[i+j]));
		if (i+100 < 100000) {
			e.push_back(make_pair(p[i+100],p[i])),e.push_back(make_pair(p[i],p[i+100]));
		}
	}
	
	e.push_back(make_pair(p[5678],p[5678]));
	
	e.push_back(make_pair(p[7678],p[7678]));
	
	random_shuffle(e.begin(),e.end());
	for (int i=0; i<(int)e.size(); ++i) printf("%d %d\n",e[i].first,e[i].second);
}

int main(){	
	make_random_test(MAXN,2*MAXN);
	make_random_test(MAXN,2*MAXN);
	make_random_test(MAXN,2*MAXN);
	make_random_test(MAXN,3*MAXN);
	make_random_test(MAXN,3*MAXN);
	make_random_test(MAXN,3*MAXN);
	
	make_special_test_1(10);
	make_special_test_1(100);
	make_special_test_1(1000);
	make_special_test_1(10000);
	make_special_test_1(100000);
	
	make_special_test_2(10);
	make_special_test_2(100);
	make_special_test_2(1000);
	make_special_test_2(10000);
	make_special_test_2(100000);
	
	make_special_test_3(100000,5);
	make_special_test_3(100000,10);
	make_special_test_3(100000,100);
	
	make_special_test_4();
	make_special_test_5();
	make_special_test_6();
	
	return 0;	
}
