#include<bits/stdc++.h> using namespace std;

int read(){ int ans = 0, f = 1; char ch = getchar(); while(!isdigit(ch)){ f = (ch=='-') ? -1 : 1; ch = getchar(); } while(isdigit(ch)){ ans = (ans<<1)+(ans<<3)+(ch^48); ch = getchar(); } return ans*f; }

const int MAXX = 5e3; int n, m, sum; int g[MAXX][MAXX], flag[MAXX];

void dfs(int x){ if(sum>n) return; sum++; flag[x] = 1; if(x == 1) printf("1"); else printf("-%d",x); int t = 0; for(int i=1; i<=n; i++){ if(g[x][i]==1 && (!flag[i])){ dfs(i); } } }

queue q;

void bfs(){ flag[1] = 1; q.push(1); sum++; while(sum<n){ if(q.empty()){ for(int i=1; i<=n; i++){ if(!flag[i]){ q.push(i); flag[i] = 1; sum++; } } } int x = q.front(); for(int i=1; i<=n; i++){ if(g[x][i]==1 && (!flag[i])){ q.push(i); flag[i] = 1; sum++; } } if(x == 1) printf("1"); else{ printf("-%d", q.front()); } q.pop(); } while(!q.empty()){ printf("-%d",q.front()); q.pop(); } return; }

int main(){ n = read(), m = read(); memset(g, 0x3f, sizeof(g)); for(int i=1; i<=m; i++){ int a = read(), b = read(); g[a][b] = 1 ; g[b][a] = 1 ; } for(int i=1; i<=n; i++){ g[i][i] = 0; } dfs(1); while(sum<n){ for(int i=1; i<=n; i++){ if(!flag[i]) dfs(i); } } cout<<endl; memset(flag, 0, sizeof(flag)); sum = 0; bfs(); return 0; }