지도 복원

전설에 따르면 비트란디아의 옛 수도 빌카미에스티스에서는 교차로마다 다른 도로가 최대 5개까지 만났다.

빌카미에스티스가 수도 지위를 잃은 뒤 도시는 재설계되어, 모든 교차로에서 도로가 정확히 3개씩 만나게 되었다. 연구자들은 도로가 다음과 같이 바뀌었다는 것을 알아냈다.

는 로 바뀌었다.

는 로 바뀌었다.

는 로 바뀌었다.

는 로 바뀌었다.

마지막으로 는 로 바뀌었다.

연구자들이 옛 도로 배치를 복원하도록 도와라. 교차로 유형, 즉 교차하는 도로 수별로 옛 수도에 교차로가 몇 개씩 있었는지 적어라.

주어진 도로 지도에서 재설계 전 교차로 중 도로가 1개, 2개, 3개, 4개, 5개인 교차로가 각각 몇 개인지 세어라.

첫 줄에 현재 도시의 교차로 수 $N$과 도로 수 $M$이 주어진다. 이어지는 $M$개의 줄에는 공백으로 구분된 두 정수 $a_i$, $b_i$가 주어지며, 이는 $a_i$번 교차로와 $b_i$번 교차로가 도로로 연결되어 있음을 뜻한다.

주어진 도시는 평면에 그릴 수 없을 수도 있다. 원래 도시에서는 두 교차로 사이에 도로가 하나만 있을 수 있었고, 도로의 양 끝이 같은 교차로에 놓일 수는 없었다.

$i$번째 줄에 원래 도시에서 정확히 $i$개의 도로가 교차하는 교차로의 수를 출력한다 ($1 \le i \le 5$).

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