TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7853
  • 题目
  • P7853果果的朋友圈
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 256MB
    问题描述

    果果所在的社交网络中有 \(n\) 个用户,有 \(m\) 对好友关系,对于每个,用户 \(a_i\)\(b_i\) 之间有一条无向边,表示他俩互为好友关系,定义若用户是用户可能认识的人需要满足以下条件:

    • \(a\ne b\)

    • \(a\)\(b\) 不是好友关系

    • 存在一个序列 \(p_1,p_2,\dots,p_l\),满足 \(p_1=a,p_l=b\),对于每个 \(i=1,2,\dots,l-1\),用户 \(p_i\)\(p_{i + 1}\) 互为好友关系。

    果果想知道在这个社交网络中每个用户有多少可能认识的人。

    对于所有用户 \(i=1,2,\dots,n\),输出一个整数表示用户有多少个可能认识的人。

    输入格式

    第一行,两个整数 \(n,m(2\le n \le 10^5,0\le m \le 10^5)\)

    接下来行,每行两个正整数 \(a_i,b_i(1\le a_i,b_i\le n,a_i\ne b_i)\),表示用户 \(a_i\) 和用户 \(b_i\) 互为好友关系。

    说明:数据保证无重边无自环。

    输出格式

    输出一行 \(n\) 个整数用空格隔开,分别表示用户 \(i,i+1,\dots,n\) 可能认识的人的数量。

    样例输入

    4 4
    2 1
    1 3
    3 2
    3 4

    样例输出

    1 1 0 2