#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<set>
#include<map>
#include<bits/stdc++.h>

#define ll long long
#define all(x) begin(x),end(x)
#define pb(x) push_back(x)
#define INPUT "input.txt"
#define OUTPUT "output.txt"


using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;

vi a(22);
vi b(22);
int n,m;

void remake(){
    for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==a[j])
				b[i]=j;
		}
	}
}

int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;
	a.resize(n+1);
	b.resize(n+1);
	for(int i=1;i<=n;i++)
		a[i]=i;
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		swap(a[x],a[y]);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==a[j])
				b[i]=j;
		}
	}
	for(int i:b)
			cout<<i<<" ";
		cout<<endl;
	for(int i=1;i<n;i++){
		if(a[i]!=i){
		    if(b[i]!=n-1)
		        cout<<b[i]<<" "<<n-1<<endl;
			swap(a[b[i]],a[n-1]);

			remake();
		    if(n-1!=a[n-1])
		        cout<<n-1<<" "<<a[n-1]<<endl;
			swap(a[n-1],a[a[n-1]]);
			remake();
		}

	}
	return 0;
}