#include<vector>

using namespace std; 

const int N = 3e7 + 10;
int ans[N];
vector<int> gp[4];

bool check(int x1, int x2, int x3, int x4){
	if(x1 == x3 || x1 == x4 || x2 == x3 || x2 == x4) return 0;
	return 1;
}

int* find_pairs(int n, int m, int u[], int v[]){
	for(int i = 0; i < m; i++) ans[i] = -1;
	for(int i = 0; i < m; i++){
		if(u[i] == u[1] && v[i] == v[1]){
			gp[0].push_back(i);
		}
		else if(u[i] == u[1] || v[i] == u[1]){
			gp[1].push_back(i);
		}
		else if(u[i] == v[1] || v[i] == v[1]){
			gp[2].push_back(i);
		}
		else{
			gp[3].push_back(i);
		}
	}
	if(gp[3].size()) ans[1] = gp[3][0];
	for(int i: gp[3]){
		ans[i] = 1;
	}
	for(int i: gp[1]){
		for(int j: gp[2]){
			if(check(u[i], v[i], u[j], v[j])){
				ans[i] = j;
				break;
			}
		}
		if(ans[i] == 0){
			for(int j: gp[3]){
				if(check(u[i], v[i], u[j], v[j])){
					ans[i] = j;
					break;
				}
			}
		}
	}
	for(int i: gp[2]){
		for(int j: gp[1]){
			if(check(u[i], v[i], u[j], v[j])){
				ans[i] = j;
				break;
			}
		}
		if(ans[i] == 0){
			for(int j: gp[3]){
				if(check(u[i], v[i], u[j], v[j])){
					ans[i] = j;
					break;
				}
			}
		}
	}
	return ans;
}