#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define N 40000

int n, m, a, b, x, post, vertex[N];
vector <int> v[N],
new_graph[N],
vertices_scc[N],
scc[N];
int st[N], rst, roz, SCC[N], scc_counter;
bool odw[N], odw_scc[N], odw_top[N], CZY[N];

int sec(int x)
{
	if (x % 2 == 0) return x - 1;
	else return x + 1;
}

void in()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d", &a, &b);
		v[a].pb(sec(b));
		v[b].pb(sec(a));
	}
}

void dfs(int x)
{
	odw[x] = true;
	//printf("X: %d\n", x);

	for (int i = 0; i < (int) v[x].size(); i++)
	{
		new_graph[v[x][i]].pb(x);
		if (odw[v[x][i]] == false)
			dfs(v[x][i]);
	}

	st[rst++] = x;
}

void dfs_scc(int x)
{
	odw_scc[x] = true;
	vertices_scc[scc_counter].pb(x);
	SCC[x] = scc_counter;

	for (int i = 0; i < (int) new_graph[x].size(); i++)
	{
		if (odw_scc[new_graph[x][i]] == false)
			dfs_scc(new_graph[x][i]);
	}
}

void clear_st()
{
	while (rst != -1)
	{
		rst--;
		if (odw_scc[st[rst]] == false && st[rst] != 0)
			dfs_scc(st[rst]),
			scc_counter++;
	}
}


void make_scc()
{
	for (int i = 1; i <= 2 * n; i++)
	{
		for (int j = 0; j < (int) v[i].size(); j++)
		{
			if (SCC[i] != SCC[v[i][j]])
				scc[SCC[i]].pb(SCC[v[i][j]]);
		}
	}
}

void topological_dfs(int x)
{
	odw_top[x] = true;
	for (int i = 0; i < (int) scc[x].size(); i++)
	{
		if (odw_top[scc[x][i]] == false)
			topological_dfs(scc[x][i]);
	}
	post++;
	vertex[post] = x;
}

void topological_sort()
{
	for (int i = 0; i < scc_counter; i++)
		if (odw_top[i] == false)
			topological_dfs(i);
}

void kurwa_dosc()
{
	for (int i = 0; i <= scc_counter; i++)
	{
		if (CZY[i] == 0)
		{
			for (int j = 0; j < (int) vertices_scc[i].size(); j++)
			{
				CZY[SCC[sec(vertices_scc[i][j])]] = -1;
			}

			for (int j = 0; j < (int) scc[j].size(); j++)
			{
				CZY[scc[i][j]] = -1;
			}
		}
	}

	for (int i = 0; i <= scc_counter; i++)
	{
		if (CZY[i] == 0)
			for (int j = 0; j < (int) vertices_scc[i].size(); j++)
			{
				printf("%d\n", vertices_scc[i][j]);
			}
	}
}

int main()
{
	in();

	for (int i = 1; i <= 2 * n; i++)
		if (odw[i] == false)
			dfs(i), clear_st();

	make_scc();
	kurwa_dosc();
}