#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <fstream>  // библиотека для ввода вывода в файл

using namespace std;

const double p = 0.2; // вероятность из условия


main() {
	ofstream value, iter_num;
	value.open("value.txt");
	iter_num.open("iter.txt");
	int n, m; // количество вершин   количество ребер
	vector<vector<int> > graph; // граф, хранимый в матрице смежности
	bool visited[100000];
	for(int i = 0; i < 100000; i++) {
		visited[i] = 0;
	}
	//ввод графа
	graph = vector<vector<int> > (n + 1, vector<int> ());
	cin >> n >> m; // количество вершин и ребер
	for(int i = 0; i < m; i++) {
		//между l и r есть ребро
		int from, to;
		cin >> from >> to;
		graph[from].push_back(to);
		graph[to].push_back(from);
	}


  //производим обход графа в ширину
  queue<int> queue_; // очередь нужная для обхода в ширину, в ней хранятся вершины, которые ждут обработки, после обработки вершина удаляется из очереди.
  int start = 1; // стартовая вершина
  queue_.push(start); // помещаем стартовую вершину в очередь для обработки

  int iteration = 0; // номер текущей итерации

  // пока в очереди есть вершины для обработки выполняем алгоритм
  while(!queue_.empty()) {
		int vertex = queue_.front(); // берем первую из очереди вершину v

		queue_.pop(); //  удаляем ее из очереди
		visited[vertex] = 1; // помечаем вершину посещенной
		iter_num << iteration++ << endl; // в файл it.txt вывожу номер итерации
		value << queue_.size() + 1 << endl; // в файл val.txt вывожу размер очереди, делаю q.size() + 1, т.к до этого была удалена вершина

		// проходим по всем вершинам соединенным с текущей
		for(int i = 0; i < graph[vertex].size(); i++) {
			int to = graph[vertex][i]; // вершина соединенная с текущей вершиной v
			if(!visited[to]) { // если вершина не посещена, то рассматриваем ее
				double prob = rand() / RAND_MAX; // получаем какое то число от 0 до 1
				if(prob <= p) { // с вероятностью p мы проходим условие
					queue_.push(to); // помещаем вершину to в очередь для обработки
				}
			}
		}
  }
}