分数: 300 点
问题陈述
有 N 研究人员,编号 1, 2, \ldots, N.
有 M 研究人员之间的利益冲突;为了 i = 1, 2, \ldots, M,研究人员 A_i 和 B_i 彼此之间存在利益冲突。
论文的审稿人必须是三名不同的研究人员,他们与论文的作者不同,并且与作者没有利益冲突。
对于 i = 1, 2, \ldots, N,解决以下问题:
- 查找研究人员撰写的论文可能的审稿人三元组的数量 i.
假设所有论文均为单一作者。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq N
- A_i \neq B_i
- (A_i, B_i) \neq (A_j, B_j) if i \neq j.
- (A_i, B_i) \neq (B_j, A_j) if i \neq j.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
输出
打印以下问题的答案 i = 1, 2, \ldots, N 按此顺序,用空格分隔。
示例输入 1
6 5 1 2 1 4 2 3 5 3 3 1
示例输出 1
0 1 0 4 4 10
下面,我们用一组数字代表一组研究人员。
-
研究人员撰写的论文不可能有三重审稿人 1.
-
研究人员撰写的论文可能有三重审稿人 2 is \lbrace 4, 5, 6 \rbrace,即 1 三重。
-
研究人员撰写的论文不可能有三重审稿人 3.
-
研究人员撰写的论文可能有三重审稿人 4 是 \lbrace 2, 3, 5 \rbrace, \lbrace 2, 3, 6 \rbrace, \lbrace 2, 5, 6 \rbrace, \lbrace 3, 5, 6 \rbrace,即 4 三倍。
-
研究人员撰写的论文可能有三重审稿人 5 是 \lbrace 1, 2, 4 \rbrace, \lbrace 1, 2, 6 \rbrace, \lbrace 1, 4, 6 \rbrace, \lbrace 2, 4, 6 \rbrace,即 4 三倍。
-
研究人员撰写的论文可能有三重审稿人 6 是 \lbrace 1, 2, 3 \rbrace, \lbrace 1, 2, 4 \rbrace, \lbrace 1, 2, 5 \rbrace, \lbrace 1, 3, 4 \rbrace, \lbrace 1, 3, 5 \rbrace, \lbrace 1, 4, 5 \rbrace, \lbrace 2, 3, 4 \rbrace, \lbrace 2, 3, 5 \rbrace, \lbrace 2, 4, 5 \rbrace, \lbrace 3, 4, 5 \rbrace,即 10 三倍。
示例输入 2
7 3 1 2 3 4 5 6
示例输出 2
10 10 10 10 10 10 20
示例输入 3
6 9 3 6 2 5 2 3 4 3 1 5 6 2 3 1 5 3 2 4
示例输出 3
1 0 0 1 0 1