#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

const int N=510,M=100010,INF=0x3f3f3f3f;

int n,m;
int g[N][N];
bool st[N];

/*
struct Node//带权
{
    int id;//编号
    int w;//权值
    Node* next;
    Node(int _id, int _w) : id(_id), w(_w), next(NULL){}

}*head[N];

void add(int a,int b,int w)//带权
{
    Node* p=new Node(b,w);
    p->next=head[a];
    head[a]=p;
}
*/

struct Node
{
    int id;//编号
    Node* next;
    Node(int _id) : id(_id), next(NULL) {}

}*head[N];

void add(int a,int b)
{
    Node* p=new Node(b);
    p->next=head[a];
    head[a]=p;
}
/*
void convert()//邻接矩阵转换邻接表
{
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
       if(g[i][j]<INF/2)
       add(i,j,g[i][j]);
}

void convert()//邻接表转换邻接矩阵
{
    for(int i=1;i<=n;i++)
    {
        for(auto p=head[i];p;p=p->next)
        {
            int j=p->id;
            g[i][j]=g[j][i]=p->w;

        }
    }
}

int main()//邻接矩阵转邻接表
{
    memset(g,0x3f,sizeof g);
    cin>>n>>m;
    while(m--)
    {
        int a,b,w;
        cin>>a>>b>>w;
        g[a][b]=g[b][a]=min(g[a][b],w);
    }

    puts("邻接矩阵表示法：");
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        if(g[i][j]>INF/2)cout<<'~'<<' ';
        else cout<<g[i][j]<<' ';
        cout<<endl;
    }

    convert();

    puts("\n邻接表表示法（括号内是权值）：");
     for(int i=1;i<=n;i++)
     {
         printf("与%d相连的边有：", i);
         for(auto p=head[i];p;p=p->next)
         printf("%d(%d)",p->id,p->w);

         cout<<endl;
     }
    return 0;
}

int main()//邻接表转邻接矩阵
{
    memset(g,0x3f,sizeof g);
    cin>>n>>m;
    while(m--)
    {
        int a,b,w;
        cin>>a>>b>>w;
        // 假设没有重边
        add(a,b,w);//无向图
        add(b,a,w);
    }

    puts("邻接表表示法（括号内是权值）：");
     for(int i=1;i<=n;i++)
     {
         printf("与%d相连的边有：", i);
         for(auto p=head[i];p;p=p->next)
         printf("%d(%d)",p->id,p->w);

         cout<<endl;
     }

    convert();

    puts("\n邻接矩阵表示法：");
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        if(g[i][j]>INF/2)cout<<'~'<<' ';
        else cout<<g[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}

void dfs(int u)//用邻接表存的带权有向图的dfs
{
    st[u]=true;
    cout<<u<<' ';
    for(Node*p=head[u];p;p=p->next)
     if(!st[p->id])
     dfs(p->id);
}

int main()//用邻接表存的带权有向图的dfs
{
    memset(g,0x3f,sizeof(g));
    cin>>n>>m;
    while(m--)
    {
     int a,b,w;
     cin>>a>>b>>w;
     add(a,b,w);
    }

    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        dfs(i);
    }
    return 0;

}

void dfs(int u)//dfs邻接表
{
    st[u]=true;
    cout<<u<<' ';
    for(Node*p=head[u];p;p=p->next)
     if(!st[p->id])
     dfs(p->id);
}

int main()//dfs邻接表
{
    memset(g,0x3f,sizeof(g));
    cin>>n>>m;
    while(m--)
    {
     int a,b;
     cin>>a>>b;
     add(a,b);
    }

    for(int i=1;i<=n;i++)
    {
        printf("%d: ",i);
        for(Node* p=head[i];p;p=p->next)
        printf("%d -> ",p->id);
        puts("NULL");
    }

    puts("-----------------------");

    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        dfs(i);
    }
    return 0;

}

void dfs(int u)//dfs邻接矩阵
{
    st[u]=true;
    cout<<u<<' ';
    for(int j=1;j<=n;j++)
    if(g[u][j]&&!st[j])
    dfs(j);

}

int main()//dfs邻接矩阵
{
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
    }

    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++)
            cout << g[i][j] << ' ';
        cout << endl;
    }
    puts("----------------");

    for (int i = 1; i <= n; i ++)
        if (!st[i])
            dfs(i);

    return 0;
}

void dfs(int u)//深搜非递归实现
{
    stack<int> s;
    s.push(u);

    while(s.size())
    {
        int t=s.top();
        s.pop();

        if(st[t]) continue;

        cout<<t<<' ';
        st[t]=true;

        for(Node* p=head[t];p;p=p->next)
        {
            int j=p->id;
            if(!st[j])
              s.push(j);
        }
    }
}

int main()//dfs非递归实现
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d: ",i);
        for(Node* p=head[i];p;p=p->next)
           printf("%d -> ",p->id);

         puts("NULL");
    }

    puts("--------------------");

    for(int i=1;i<=n;i++)
        if(!st[i])
        dfs(i);
    return 0;
}
*/
void bfs(int u)//bfs
{
    queue<int> q;
    q.push(u);
    st[u]=true;

    while(q.size())
    {
        int t=q.front();
        q.pop();

        cout<<t<<' ';

        for(Node* p=head[t];p;p=p->next)
        {
            int j=p->id;
            if(!st[j])
            {
               st[j]=true;
               q.push(j);
            }
        }
    }
}

int main()//bfs
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    for(int i=1;i<=n;i++)
    if(!st[i])
      bfs(i);

    return 0;
}