← 返回题目列表

AtCoder · abc442_c

E. 同行评审

中文机器翻译题面 查看原题

分数: 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