#include<bits/stdc++.h>
using namespace std;
vector<int>G[100];
int visited[100],c=0,k=0;

void dfs(int x)
{
    for(k=0; k<G[x].size(); k++)
    {
        if(visited[G[x][k]]==0)
        {
            visited[G[x][k]]=1;

            int v=G[x][k];
            //  cout<<v<<endl;
            dfs(v);
        }

    }

    printf("%d %d\n",x,visited[G[x][k]]);
}

int main()
{
    int m,n,i,j,x,y;
    cin>>m>>n;

    for(i=0; i<m; i++)
    {
        cin>>x>>y;

        G[x].push_back(y);
        G[y].push_back(x);

    }

    memset(visited,0,sizeof(visited));


    dfs(n);

    return 0;

}