AT_abc442_c.[ABC442C] Peer Review

入门

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

有 NN 名研究员,编号为 1,2,…,N1, 2, \dots, N。

这些研究员之间存在 MM 对利益冲突;对于 i=1,2,…,Mi = 1, 2, \dots, M,研究员 AiA_i 与 BiB_i 互有利益冲突。

一篇论文的审稿人必须由三名不同的研究员担任,且这三名审稿人必须既不是该论文的作者,也与作者没有任何利益冲突。

请针对 i=1,2,…,Ni = 1, 2, \dots, N,分别解决以下问题:
求出当论文作者为研究员 ii 时,可能的审稿人三人组的数量。
假设所有论文均为单作者。

输入格式

输入从标准输入按以下格式给出:

NN MM

A1A_1 B1B_1

A2A_2 B2B_2

⋮\vdots

AMA_M BMB_M

限制条件

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 0≤M≤2×1050 \le M \le 2 \times 10^5
  • 1≤Ai,Bi≤N1 \le A_i, B_i \le N
  • Ai≠BiA_i \ne B_i
  • 若 i≠ji \ne j,则 (Ai,Bi)≠(Aj,Bj)(A_i, B_i) \ne (A_j, B_j)。
  • 若 i≠ji \ne j,则 (Ai,Bi)≠(Bj,Aj)(A_i, B_i) \ne (B_j, A_j)。
  • 所有输入均为整数。

输出格式

按 i=1,2,…,Ni = 1, 2, \dots, N 的顺序输出对应的答案,中间用空格分隔。

输入输出样例

  • 输入#1

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

    输出#1

    0 1 0 4 4 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

说明/提示

样例 1 解释

下文中,我们用研究员编号的集合来表示一组研究员。

  • 对于研究员 11 创作的论文,不存在可能的审稿人三人组。
  • 对于研究员 22 创作的论文,可能的审稿人三人组为 {4,5,6}\{4, 5, 6\},共 11 组。
  • 对于研究员 33 创作的论文,不存在可能的审稿人三人组。
  • 对于研究员 44 创作的论文,可能的审稿人三人组为 {2,3,5},{2,3,6},{2,5,6},{3,5,6}\{2, 3, 5\}, \{2, 3, 6\}, \{2, 5, 6\}, \{3, 5, 6\},共 44 组。
  • 对于研究员 55 创作的论文,可能的审稿人三人组为 {1,2,4},{1,2,6},{1,4,6},{2,4,6}\{1, 2, 4\}, \{1, 2, 6\}, \{1, 4, 6\}, \{2, 4, 6\},共 44 组。
  • 对于研究员 66 创作的论文,可能的审稿人三人组为 {1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}\{1, 2, 3\}, \{1, 2, 4\}, \{1, 2, 5\}, \{1, 3, 4\}, \{1, 3, 5\}, \{1, 4, 5\}, \{2, 3, 4\}, \{2, 3, 5\}, \{2, 4, 5\}, \{3, 4, 5\},共 1010 组。

输入解题思路,AI测评打分。不知道怎么写?

首页