3. Zanedbané zastávky

Kocúrkovo je to pravé mesto pre ľudí, ktorí sa vedia stratiť aj vo vlastnom byte. Je to totiž len jedna veľmi dlhá ulica. A keďže je taká dlhá, už roky tu jazdí mestská hromadná doprava.

Miestne autobusy jazdia po Kocúrkove tak, ako by ste od dlhej, rovnej ulice čakali. Pozdĺž ulice je postavených \(n\) autobusových zastávok. Každá autobusová linka má dve konečné zastávky, medzi ktorými jej autobusy jazdia hore-dolu, pričom stoja aj na každej zastávke po ceste. Kocúrkovo je však Kocúrkovo a tak sa môže stať, že niektoré linky začínajú aj končia na rovnakej zastávke (a teda ich autobusy iba stoja na tejto zastávke).

Kocúrkovské zastávky začali pod náporom neúprosného času hrdzavieť a chátrať. Preto si starosta Kocúrkova povedal, že ich dá všetky zrekonštruovať. A keď už sa prerábajú, tak by to malo byť vidno. Nech na to ľudia do volieb nezabudnú.

Rekonštrukcia jednej zastávky trvá jeden deň. Je možné rekonštruovať aj viac zastávok naraz. Starosta by teda mohol všetky zastávky nechať zrekonštruovať v ten istý deň, ale pre jeho volebné preferencie to nemusí byť tá najlepšia možnosť. Ľudia si totiž rekonštrukciu budú pamätať lepšie, ak bude prebiehať dlhšie.

Starostovi hrá do karát to, že Kocúrkovo je známe svojimi klebetníkni. Stačí, aby sa na trase autobusovej linky prerábala jediná zastávka a v autobuse vrava neutíchne až do večera. Ak sa teda v nejaký deň na trase každej linky prerába aspoň jedna zastávka, v celej Kocúrkovskej hromadnej doprave sa rozpráva iba o rekonštrukcii.

Úloha

Máte zadaný počet zastávok v Kocúrkove, počet liniek MHD a konečné zastávky, medzi ktorými tieto linky premávajú.

Starosta chce naplánovať rekonštrukciu zastávok tak, aby sa čo najdlhšie v autobusoch hovorilo iba o nej. Chce teda, aby od začiatku rekonštrukcie čo najdlhšie platilo, že na trase každej linky sa prerába aspoň jedna zastávka. Povedané ešte inak, starosta chce, aby sa čo najneskôr stalo, že na trase niektorej linky sa nebude prerábať žiadna zastávka.

A tu prichádzate na rad vy. Nájdite pre starostu Kocúrkova takýto plán a povedzte mu, koľko dní bude pri každej linke MHD aspoň jedna zastávka v rekonštrukcii. Pre každú zastávku teda naplánujte, v ktorý deň sa má prerábať.

Formát vstupu

V prvom riadku vstupu sú dve medzerou oddelené celé čísla \(n\) a \(m\) - počet zastávok a počet autobusových liniek. Platí \(1 \leq n \leq 1\, 000\, 000\) a \(1 \leq m \leq 100\, 000\).

Nasleduje \(m\) riadkov, v každom z nich sú dve medzerou oddelené čísla \(z_i\) a \(k_i\) - poradové čísla konečných zastávok \(i\)-tej linky, od začiatku mesta. Platí \(1 \leq z_i \leq k_i \leq n\).

Formát výstupu

Na prvý riadok výstupu vypíšte jedno číslo - po koľko dní od začiatku vieme rekonštruovať aspoň jednu zastávku na trase každej linky.

Na druhý riadok vypíšte \(n\) medzerou oddelených čísel - čísla dní, kedy sa majú rekonštruovať jednotlivé zastávky (v poradí od začiatku mesta po koniec). Rekonštrukcia sa začína nultým (\(0\)) dňom. Ak existuje viac optimálnych riešení, vypíšte ľubovoľné z nich.

Príklady

Input:

5 3
1 3
2 5
4 5

Output:

2
1 0 2 1 0

Na trase prvej linky sa zastávky rekonštruujú v deň \(1\), \(0\) a \(2\), takže ľudia si budú rekonštrukciu všímať \(3\) dni. Podobne druhá linka. Pri tretej sa rekonštruuje v dni \(0\) a \(1\). Všetci si teda budú starostovu rekonštrukciu všímať aspoň \(2\) dni.