#include <bits/stdc++.h> // библиотке включает почти все что может пригодиться
#include <fstream>  // библиотека для ввода вывода в файл

using namespace std;

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


int n, m; // количество вершин   количество ребер
vector<vector<int> > gr(100000); // граф, хранимый в матрице смежности
bool vis[100000]; // массив посещенности, если vis[i] = 0 значит вершина i не была посещена, если vis[i] = 1 значит вершина i была посещена
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // генератор случайных чисел

// функция возвращает число от 0 до 1, она генерирует случайное число и делит его на максимальное возможное
double get_prob() {
	return ((double)rng() / rng.max());
}

main() {

	//вывод в файл
	ofstream it; // номера итерации
	it.open("it.txt");
	ofstream val; // размеры очереди
	val.open("val.txt");

	//ввод графа
	cin >> n >> m; // количество вершин и ребер
	for(int i = 0; i < m; i++) {
		//между l и r есть ребро
		int l, r;
		cin >> l >> r;
		gr[l].push_back(r);
		gr[r].push_back(l);
	}


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

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

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

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

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