P7853果果的朋友圈 | ||
|
问题描述
果果所在的社交网络中有 \(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