题目描述

33DAI 的班里有 $n$ 个同学，编号从 $1$ 到 $n$。班里有 $m$ 对朋友，朋友关系是相互的，同一对同学至多出现一次。

对每个同学 $u$，33DAI 想知道：有多少个同学 $v$ 满足下面两个条件？

• $u$ 和 $v$ 不是朋友；
• 存在一个同学 $w$，使得 $u$ 和 $w$ 是朋友，且 $v$ 和 $w$ 也是朋友。

换句话说，$u$ 和 $v$ 之间隔着恰好一个同学。

输入格式

第一行两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行两个整数 $u, v$（$1 \le u < v \le n$），表示 $u$ 和 $v$ 是朋友。

输出格式

输出一行 $n$ 个整数，相邻两个整数之间用一个空格隔开，第 $u$ 个整数表示与 $u$ 隔着恰好一个同学的人数。

4 2
1 2
2 3

1 0 1 0

样例 1 解释

• $1$ 号同学和 $2$ 号是朋友；$2$ 号还和 $3$ 号是朋友，所以 $1$ 号与 $3$ 号隔着同学 $2$，$1$ 号的答案是 $1$。
• $2$ 号的朋友是 $1$ 号和 $3$ 号，没有"隔一个人"的同学，答案是 $0$。
• $3$ 号与 $1$ 号隔着同学 $2$，答案是 $1$。
• $4$ 号谁也不认识，答案是 $0$。

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

2 2 2 2 2 2

样例 2 解释

这 $6$ 个同学围成一个环。以 $1$ 号为例：$1$ 号的朋友是 $2$ 号和 $6$ 号，$2$ 号的朋友还有 $3$ 号、$6$ 号的朋友还有 $5$ 号，所以 $1$ 号与 $3$ 号、$5$ 号都隔着恰好一个同学，答案是 $2$。其余同学同理，答案都是 $2$。

样例 3

见 hop3.in 与 hop3.ans。

样例 4

见 hop4.in 与 hop4.ans。

数据范围

对于全部测试数据，保证：

• $1 \le n \le 5000$；
• $0 \le m \le \min\left(5000, \frac{n(n-1)}{2}\right)$；
• 每条朋友关系满足 $1 \le u < v \le n$，且同一对同学至多出现一次。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。