Žemėlapio atkūrimas

Legendos byloja, kad Bitlandijos istorinėje sostinėje Vilkamiestyje gatvės susikirsdavo sankryžose su ne daugiau kaip $5$ kitomis gatvėmis.

Vilkamiesčiui praradus sostinės vardą, miestas buvo perprojektuotas, t. y. sankryžos buvo atnaujintos į tokias, kuriose susikirstų lygiai $3$ gatvės. Tyrinėtojams pavyko atkurti, kad gatvių pakeitimas vyko taip:

buvo pakeista į ,

į ,

į ,

į ,

ir, galiausiai, į .

Padėkite tyrinėtojams atkurti senąjį gatvių išsidėstymą, surašydami, kiek kokio tipo (t. y. su kokiu susikertančių gatvių skaičiumi) sankryžų buvo senojoje sostinėje.

Duotas gatvių žemėlapis. Suskaičiuokite, kiek sankryžų prieš miesto perprojektavimą buvo su viena gatve, kiek su dviem, kiek su trimis, kiek su keturiomis ir kiek su penkiomis gatvėmis.

Pirmoje eilutėje pateikti $N$ ir $M$ – dabartiniai miesto sankryžų ir gatvių skaičiai. Likusiose $M$ eilučių pateikiama po du tarpais atskirtus skaičius $a_i $ir $b_i$, kurie reiškia, kad $a_i$-toji ir $b_i$-toji sankryžos yra sujungtos gatve.

Duotą miestą nebūtinai įmanoma išdėstyti plokštumoje. Pradiniame mieste tarp dviejų sankryžų galėjo būti tik viena gatvė, o abu gatvės galai toje pačioje sankryžoje būti negalėjo.

$i$-toje eilutėje išveskite keliose pradinio miesto sankryžose susikirto lygiai $i$ gatvių ($1 ≤ i ≤ 5$).

• $10 ≤ N ≤ 200\, 000$
• $15 ≤ M ≤ 300\, 000$
• $1 ≤ a_i , b_i ≤ N$ ($1 ≤ i ≤ M$)