#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

ifstream cin("prob5.in");
ofstream cout("prob5.out");

int n, m, comp, Max, Nod, minNod = 100000, maxNod, k, ans;
vector<int> a[100010], need;
bool viz[100010];
queue<int> q;

void dfs(int nod, bool write = 0) {
	need.push_back(nod);
	k++;
	if(write)
		cout << nod << ' ';
	viz[nod] = 1;
	for(int i=0; i<a[nod].size(); i++)
		if(!viz[a[nod][i]])
			dfs(a[nod][i], write);
}

void bfs(int nod) {
	cout << nod << ' ';
	viz[nod] = 1;
    q.push(nod);
    while(!q.empty()) {
        nod = q.front();
        q.pop();
        for(auto &x: a[nod])
            if(!viz[x])
            	viz[x] = 1,
                cout << x << ' ',
                q.push(x);
    }
}

int main() {
	cin >> n >> m;
	while(m--) {
		int x, y;
		cin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}

//--------------------------------------------------------------------------------

	cout << "DFS:\n";
	for(int i=1; i<=n; i++)
		if(!viz[i])
			dfs(i, 1),
			comp++,
			cout << '\n';
	cout << "Nr de comp conexe: " << comp << "\n\n";

//--------------------------------------------------------------------------------

	cout << "BFS:\n";
	for(int i=1; i<=n; i++)
		viz[i] = 0,
		Max = max(Max, int(a[i].size()));

	for(int i=1; i<=n; i++)
		if(!viz[i])
			bfs(i),
			cout << '\n';
	cout << '\n';

//--------------------------------------------------------------------------------

	cout << "Gradul MAX: " << Max << '\n';
	cout << "Nodurile cu gradul MAX: ";
	for(int i=1; i<=n; i++)
		if(a[i].size() == Max)
			cout << i << ' ';
	cout << '\n';

	for(int i=1; i<=n; i++)
		viz[i] = 0;

//--------------------------------------------------------------------------------

	for(int i=1; i<=n; i++)
		if(!viz[i])
			k = 0,
			dfs(i),
			maxNod = max(maxNod, k),
			minNod = min(minNod, k);

	for(int i=1; i<=n; i++)
		viz[i] = 0;

	cout << '\n';

//--------------------------------------------------------------------------------

	cout << "Grad MIN al comp conexe: " << minNod << '\n';

	for(int i=1; i<=n; i++)
		if(!viz[i]) {
			k = 0,
			dfs(i);
			if(k == minNod)
				ans++;
		}
	cout << "Nr de comp conexe cu grad MIN: " << ans << '\n';

	for(int i=1; i<=n; i++)
		viz[i] = 0;

	cout << '\n';

//--------------------------------------------------------------------------------

	cout << "Grad MAX al comp conexe: " << maxNod << '\n';
	ans = 0;
	for(int i=1; i<=n; i++)
		if(!viz[i]) {
			k = 0,
			dfs(i);
			if(k == maxNod)
				ans++;
		}
	cout << "Nr de comp conexe cu grad MAX: " << ans << '\n';

	for(int i=1; i<=n; i++)
		viz[i] = 0;

	cout << '\n';

//--------------------------------------------------------------------------------

	cout << "Componentele cu grad maxim:\n";
	for(int i=1; i<=n; i++)
		if(!viz[i]) {
			need.clear(),
			k = 0,
			dfs(i);
			if(k == maxNod) {
				for(auto &x: need)
					cout << x << ' ';
				cout << '\n';
			}
		}
	return 0;
}