n, m = [int(_) for _ in input().split()]
susedia = [ [] for _ in range(n) ] #zoznam susedov pre kazdy vrchol
for _ in range(m):
	#spracovanie jednej hrany
	x, y = [int(_)-1 for _ in input().split()] #ocislujeme od nuly
#	print(x, y)
	#pridame susedov k obom vrcholom
	susedia[x].append(y)
	susedia[y].append(x)
print(*susedia)
 
komponenty = [ -1 for _ in range(n) ] #pole s cislami komponentu pre kazdy vrchol
pocet_komponentov = 0
 
def komponent(v): #vrati zoznam vrcholov v komponente obsahujucom vrchol v
	global komponenty
	global pocet_komponentov
	pocet_komponentov = pocet_komponentov+1
	komponenty[v] = pocet_komponentov
	zostava = [v] #vrcholy, ktore treba spracovat
	while len(zostava) > 0:
		i = zostava[0] #vyberieme jeden vrchol
		zostava = zostava[1:]
		#prejdeme vsetkych susedov vrchola i a pridame, ak este nie su
		for j in susedia[i]: #j=sused vrchola i
			if komponenty[j] == -1:
				zostava.append(j) #pridame k zoznamu vrcholov, kt.este treba spracovat
				komponenty[j] = pocet_komponentov #patri do toho isteho komponentu
 
for i in range(n):
	if komponenty[i] == -1:
		komponent(i)
print(pocet_komponentov)	
print(komponenty)
 

biwgbSA9IFtpbnQoXykgZm9yIF8gaW4gaW5wdXQoKS5zcGxpdCgpXQpzdXNlZGlhID0gWyBbXSBmb3IgXyBpbiByYW5nZShuKSBdICN6b3puYW0gc3VzZWRvdiBwcmUga2F6ZHkgdnJjaG9sCmZvciBfIGluIHJhbmdlKG0pOgoJI3NwcmFjb3ZhbmllIGplZG5laiBocmFueQoJeCwgeSA9IFtpbnQoXyktMSBmb3IgXyBpbiBpbnB1dCgpLnNwbGl0KCldICNvY2lzbHVqZW1lIG9kIG51bHkKIwlwcmludCh4LCB5KQoJI3ByaWRhbWUgc3VzZWRvdiBrIG9ib20gdnJjaG9sb20KCXN1c2VkaWFbeF0uYXBwZW5kKHkpCglzdXNlZGlhW3ldLmFwcGVuZCh4KQpwcmludCgqc3VzZWRpYSkKCmtvbXBvbmVudHkgPSBbIC0xIGZvciBfIGluIHJhbmdlKG4pIF0gI3BvbGUgcyBjaXNsYW1pIGtvbXBvbmVudHUgcHJlIGthemR5IHZyY2hvbApwb2NldF9rb21wb25lbnRvdiA9IDAKCmRlZiBrb21wb25lbnQodik6ICN2cmF0aSB6b3puYW0gdnJjaG9sb3YgdiBrb21wb25lbnRlIG9ic2FodWp1Y29tIHZyY2hvbCB2CglnbG9iYWwga29tcG9uZW50eQoJZ2xvYmFsIHBvY2V0X2tvbXBvbmVudG92Cglwb2NldF9rb21wb25lbnRvdiA9IHBvY2V0X2tvbXBvbmVudG92KzEKCWtvbXBvbmVudHlbdl0gPSBwb2NldF9rb21wb25lbnRvdgoJem9zdGF2YSA9IFt2XSAjdnJjaG9seSwga3RvcmUgdHJlYmEgc3ByYWNvdmF0Cgl3aGlsZSBsZW4oem9zdGF2YSkgPiAwOgoJCWkgPSB6b3N0YXZhWzBdICN2eWJlcmllbWUgamVkZW4gdnJjaG9sCgkJem9zdGF2YSA9IHpvc3RhdmFbMTpdCgkJI3ByZWpkZW1lIHZzZXRreWNoIHN1c2Vkb3YgdnJjaG9sYSBpIGEgcHJpZGFtZSwgYWsgZXN0ZSBuaWUgc3UKCQlmb3IgaiBpbiBzdXNlZGlhW2ldOiAjaj1zdXNlZCB2cmNob2xhIGkKCQkJaWYga29tcG9uZW50eVtqXSA9PSAtMToKCQkJCXpvc3RhdmEuYXBwZW5kKGopICNwcmlkYW1lIGsgem96bmFtdSB2cmNob2xvdiwga3QuZXN0ZSB0cmViYSBzcHJhY292YXQKCQkJCWtvbXBvbmVudHlbal0gPSBwb2NldF9rb21wb25lbnRvdiAjcGF0cmkgZG8gdG9obyBpc3RlaG8ga29tcG9uZW50dQoKZm9yIGkgaW4gcmFuZ2Uobik6CglpZiBrb21wb25lbnR5W2ldID09IC0xOgoJCWtvbXBvbmVudChpKQpwcmludChwb2NldF9rb21wb25lbnRvdikJCnByaW50KGtvbXBvbmVudHkpCg==

NCAyCjEgMgoyIDQKCjE0IDE0CjEgMgoyIDYKMiA3CjMgNQo0IDUKNCA2CjYgNwo3IDgKOCA5CjggMTAKMTEgMTIKMTEgMTMKMTIgMTQKMTMgMTQK

4 2
1 2
2 4

14 14
1 2
2 6
2 7
3 5
4 5
4 6
6 7
7 8
8 9
8 10
11 12
11 13
12 14
13 14