TouchStone
  Please Login
Login Sign Up
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P7853
  • Problem
  • P7853果果的朋友圈
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s 256MB
    Description

    果果所在的社交网络中有 \(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\),输出一个整数表示用户有多少个可能认识的人。

    Input Format

    第一行,两个整数 \(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\) 互为好友关系。

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

    Output Format

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

    Sample Input

    4 4
    2 1
    1 3
    3 2
    3 4

    Sample Output

    1 1 0 2