Žemėlapio atkūrimas

시간 제한1초메모리 제한1024 MB

요약
여러 번의 국소 변환으로 만들어진 그래프가 주어졌을 때, 변환 이전 그래프에서 각 정점의 차수가 1부터 5였던 개수를 각각 구한다.
난이도

어려움10점 중 8점

유형
그래프, 수학, 구현
정답자
아직 제출이 없습니다

문제

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

Vilkamiesčiui praradus sostinės vardą, miestas buvo perprojektuotas, t. y. sankryžos buvo atnaujintos į tokias, kuriose susikirstų lygiai 33 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 NN ir MM – dabartiniai miesto sankryžų ir gatvių skaičiai. Likusiose MM eilučių pateikiama po du tarpais atskirtus skaičius a_ia\_i ir b_ib\_i, kurie reiškia, kad a_ia\_i-toji ir b_ib\_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.

출력

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

제한

  • 10≤N≤200,00010 ≤ N ≤ 200\\, 000
  • 15≤M≤300,00015 ≤ M ≤ 300\\, 000
  • 1≤a_i,b_i≤N1 ≤ a\_i , b\_i ≤ N (1≤i≤M1 ≤ i ≤ M)

예제1

  1. 예제 1

    입력
    16 24
1 2
1 3
1 5
2 4
2 6
3 5
3 7
4 6
4 8
5 7
6 8
7 9
8 10
9 10
9 11
10 11
11 12
12 13
12 15
13 14
13 16
14 15
14 16
15 16
    예상 출력
    1
2
1
0
0