#D0270. 朋友平均有几个朋友

朋友平均有几个朋友

注意文件 IO,题目英文名见标题下方标签。

题目背景

33DAI 最近看了一个关于“公交车悖论”的视频。

题目描述

nn 位同学,编号为 1n1\sim n。他们有 mm 对好朋友关系。

请你求出所有人的朋友数量,以及他所有朋友的平均朋友数量(上取整)。

输入格式

第一行两个整数 n,mn,m

接下来 mm 行,每行两个整数 a,ba,b 表示这两个编号的人是朋友。

保证不会有重复的朋友关系,即如果存在了 3 5,则 mm 组关系中不会存在其他的 3 55 3

输出格式

输出 nn 行,第 ii 行表示编号为 ii 的同学有几个朋友,以及 ii 的朋友平均有几个朋友。

3 3
1 2
1 3
2 3
2 2 
2 2
2 2
6 10
1 2
1 3
1 4
1 5 
1 6
2 3
3 4
4 5
5 6
6 2
5 3
3 4
3 4
3 4
3 4
3 4

样例解释

样例 2 的情况如图:

每个人的朋友数量分别为:5 3 3 3 3 3

  • 11 号同学有五个朋友,每个朋友都有三个朋友。
  • 其他同学情况都一样,都有三个朋友,三个朋友的朋友数量分别是 5 3 3 (5+3+3)/3=3.666(5+3+3)/3=3.666\dots,上取整后为 44.

数据规模与约定

对于 100%100\% 的数据,2n10002\le n\le 1000n1mn×(n1)2n-1\le m\le \frac{n\times (n-1)}{2} 保证每位同学都至少有一个朋友。

  • 子任务 1(30 分):保证所有人之间都是朋友。
  • 子任务 2(30 分):保证 m=n1m=n-1,第 ii 组朋友关系是 iii+1i+1 之间为朋友。
  • 子任务 3(40 分):没有特殊限制。