#define MAX_NUM 20

typedef struct {
	int vexnum, arcnum;//顶点数和边数
	int vexs[MAX_NUM];//顶点数组
	int edges[MAX_NUM][MAX_NUM];//邻接矩阵
}MGraph;

int visit[MAX_NUM] = { 0 };
void CreateGraph(MGraph& G) {
	cin >> G.vexnum >> G.arcnum;
	for (int i = 0; i < MAX_NUM; i++) {
		for (int j = 0; j < MAX_NUM; j++) {
			G.edges[i][j] = 0;
		}
	}
	for (int i = 0; i < G.vexnum; i++) {
		G.vexs[i] = i;
	}

	int va, vb;
	for (int i = 0; i < G.arcnum; i++) {
		cin >> va >> vb;
		G.edges[va][vb] = 1;
		G.edges[vb][va] = 1;
	}
}

void DFS(MGraph& G, int n) {
	visit[n] = 1;
	cout << n << " ";
	for (int i = 0; i < G.vexnum; i++) {
		if (G.edges[n][i] == 1 && visit[i] == 0) {
			DFS(G, i);
		}
	}
}
void BFS(MGraph& G, int n) {
	visit[n] = 1;
	queue<int> s;
	s.push(n);
	while (!s.empty()) {
		int temp = s.front();
		s.pop();
		cout << temp << " ";
		for (int i = 0; i < G.vexnum; i++) {
			if (G.edges[temp][i] == 1 && visit[i] == 0) {
				visit[i] = 1;
				s.push(i);
			}
		}
	}

}
int main() {
	MGraph G;
	CreateGraph(G);

	for (int i = 0; i < G.vexnum; i++) {
		if (visit[i]) continue;
		cout << "{ ";
		DFS(G, i);
		cout << "}" << endl;
	}
	for (int i = 0; i < MAX_NUM; i++) {
		visit[i] = 0;
	}

	for (int i = 0; i < G.vexnum; i++) {
		if (visit[i])continue;
		cout << "{ ";
		BFS(G, i);
		cout << "}" << endl;
	}
	return 0;
}