#include<iostream>
#include<queue>

using namespace std;

int main()
{
    int nodes;
    cout<<"Enter Node Number: "<<endl;
    cin>> nodes;
    int graph[nodes][nodes];

    int edges;
    cout<<"Enter Edge Number: "<<endl;
    cin>> edges;

    //Graph initialization
    for(int i=0; i<nodes; i++)
    {
        for(int j=0; j<nodes; j++)
        {
            if (i==j)
            {
                graph[i][j]=0;
            }
            else
            {
                graph[i][j]=-1;
            }
        }
    }


    //Graph input not weight
    for (int i=0; i<edges; i++)
    {
        int v1, v2;
        cin >> v1 >> v2;
        graph[v1][v2]=1; // Unweighted with 2 line is undirected
        graph[v2][v1]=1; // This line for directed (Not using this line means directed)
    }


    /*
    //Graph input with weight
    for (int i=0; i<edges; i++)
    {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        graph[v1][v2]= w; // Weighted with 2 line is undirected
        graph[v2][v1]= w; // This line for directed (Not using this line means directed)
    }
    */

    //Print matrix
    for(int i=0; i<nodes; i++)
    {
        for(int j=0; j<nodes; j++)
        {
            cout<<graph[i][j]<< " ";
        }
        cout<< endl;
    }

    int root;
    cout<<"Enter Root Node: ";
    cin>> root;

    queue<int> q;
    q.push(root);

    int visited[nodes] = {0};

    while(!q.empty())
    {
        int node = q.front();
        q.pop();
        if(visited[node]) continue;
        cout<< node<< " ";
        visited[node] =1;

        for(int adj_node=0; adj_node<nodes; adj_node++)
        {
            if(graph[node][adj_node]>0 && !visited[adj_node])
            {
                q.push(adj_node);
            }
        }
    }
}