#include<iostream>
#include<fstream>

using namespace std;

ifstream fin("date.in");
ofstream fout("data.out");
template<typename T>
class Queue
{
	typedef struct nod
	{
		int info;
		nod *next;
	}queue;
	queue *first, *last;
public:
	Queue();
	~Queue();
	void push(T);
	void pop();
	T peek() const;
	T peek_possition(unsigned)const;
	void show()const;
	bool isEmpty()const;
	int size()const;
};

template<typename T>Queue<T>::Queue()
{
	first = last = NULL;
}

template<typename T>Queue<T>::~Queue()
{
	queue *elem;
	if(first)
	while (last)
	{
		elem = last;
		last = last->next;
		delete elem;
	}
}

template<typename T>void Queue<T>::push(T val)
{
	if (first == NULL)
	{
		first = new queue;
		first->info = val;
		first->next = NULL;
		last = first;
	}
	else
	{
		queue *p = new queue;
		p->info = val;
		p->next = NULL;
		first->next = p;
		first = p;
	}
}

template<typename T>void Queue<T>::show()const
{
	queue *p = last;
	while (p)
	{
		fout << p->info << " ";
		p = p->next;
	}
}

template<typename T>void Queue<T>::pop()
{
	queue *p = last;
	last = last->next;
	delete p;
}

template<typename T>T Queue<T>::peek()const
{
	return last->info;
}

template<typename T>T Queue<T>::peek_possition(unsigned possition)const
{
	int count = 1;
	queue *p = last;
	while (p && count != possition)
	{
		p = p->next;
		count++;
	}
	if (p)
		return p->info;
	else
		return -1;
}

template<typename T>bool Queue<T>::isEmpty()const
{
	if (!last)
		return true;
	else
		return false;
}

template<typename T>int Queue<T>::size()const
{
	int count = 1;
	queue *p = last;
	if (p)
		while (p)
		{
			p = p->next;
			count++;
		}
	else
		count = 0;

	return count;
}

#define NMAX 100
class Graph
{
    int edge, nods,viz[NMAX];
	Queue<int> graph[NMAX],queue;
public:
	Graph();
	~Graph();
	void adiacent_list();
	void breadth();
};

Graph::Graph()
{
	int x, y;
	fin >> nods;
	fin >> edge;
	for (unsigned int i = 1;i <= edge;i++)
	{
		fin >> x >> y;
		graph[x].push(y);
		graph[y].push(x);
	}
}

void Graph::breadth()
{
	int st, dr, i, x[50], j, p[50];
	st = dr = 1;
	for (int i = 1;i <= 49;i++)
		p[i] = 0;
	p[1] = 1; // daca vrei sa incepi cu alt nod ca start trebuie sa pui p[ nodul tau] = 1
	queue.push(1); //si il bagi in coada queue.push(nodul tau)
	while (st <= dr)
	{
		for (i = 1;i <= graph[queue.peek_possition(st)].size();i++)
		{
			j = graph[queue.peek_possition(st)].peek_possition(i);
			if (!p[j])
			{
				dr++;
				queue.push(j);
				p[j] = 1;
			}
		}
		st++;
	}

	adiacent_list();

	queue.show();
}

void Graph::adiacent_list()
{
	for (unsigned int i = 1;i <= nods;i++)
	{
		fout << i << " : ";
		while (!graph[i].isEmpty())
		{
			fout << graph[i].peek() << " ";
			graph[i].pop();
		}
		fout << endl;
	}
}

Graph::~Graph()
{
}

void main()
{
	Graph g;
	g.breadth();

	system("pause");
}