C - Peer Review Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 人の研究者がおり、研究者には 1, 2, \ldots, N の番号が付けられています。

研究者の間には M 個の利害関係があり、i = 1, 2, \ldots, M に対して研究者 A_i と研究者 B_i は互いに利害関係にあります。

論文の査読者は、その論文の著者とは異なり、著者と利害関係にない相異なる 3 人の研究者である必要があります。

i = 1, 2, \ldots, N について以下の問題を解いてください。

  • 研究者 i が著者である論文の査読者の 3 人組として考えられるものは何通りあるか求めよ。

ただし、すべての論文は単著であるものとします。

制約

  • 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
  • i \neq j のとき (A_i, B_i) \neq (A_j, B_j)
  • i \neq j のとき (A_i, B_i) \neq (B_j, A_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 が著者である論文の査読者の 3 人組として考えられるものはありません。

  • 研究者 2 が著者である論文の査読者の 3 人組として考えられるものは \lbrace 4, 5, 6 \rbrace の 1 通りです。

  • 研究者 3 が著者である論文の査読者の 3 人組として考えられるものはありません。

  • 研究者 4 が著者である論文の査読者の 3 人組として考えられるものは \lbrace 2, 3, 5 \rbrace, \lbrace 2, 3, 6 \rbrace, \lbrace 2, 5, 6 \rbrace, \lbrace 3, 5, 6 \rbrace の 4 通りです。

  • 研究者 5 が著者である論文の査読者の 3 人組として考えられるものは \lbrace 1, 2, 4 \rbrace, \lbrace 1, 2, 6 \rbrace, \lbrace 1, 4, 6 \rbrace, \lbrace 2, 4, 6 \rbrace の 4 通りです。

  • 研究者 6 が著者である論文の査読者の 3 人組として考えられるものは \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

Score : 300 points

Problem Statement

There are N researchers, numbered 1, 2, \ldots, N.

There are M conflicts of interest among the researchers; for i = 1, 2, \ldots, M, researchers A_i and B_i have a conflict of interest with each other.

The reviewers of a paper must be three distinct researchers who are different from the author of the paper and have no conflict of interest with the author.

For i = 1, 2, \ldots, N, solve the following problem:

  • Find the number of possible triples of reviewers for a paper authored by researcher i.

Assume that all papers are single-authored.

Constraints

  • 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.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

Print the answers for i = 1, 2, \ldots, N in this order, separated by spaces.

Sample Input 1

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

Sample Output 1

0 1 0 4 4 10

Below, we represent a set of researchers by the set of their numbers.

  • There are no possible triples of reviewers for a paper authored by researcher 1.

  • The possible triple of reviewers for a paper authored by researcher 2 is \lbrace 4, 5, 6 \rbrace, which is 1 triple.

  • There are no possible triples of reviewers for a paper authored by researcher 3.

  • The possible triples of reviewers for a paper authored by researcher 4 are \lbrace 2, 3, 5 \rbrace, \lbrace 2, 3, 6 \rbrace, \lbrace 2, 5, 6 \rbrace, \lbrace 3, 5, 6 \rbrace, which is 4 triples.

  • The possible triples of reviewers for a paper authored by researcher 5 are \lbrace 1, 2, 4 \rbrace, \lbrace 1, 2, 6 \rbrace, \lbrace 1, 4, 6 \rbrace, \lbrace 2, 4, 6 \rbrace, which is 4 triples.

  • The possible triples of reviewers for a paper authored by researcher 6 are \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, which is 10 triples.

Sample Input 2

7 3
1 2
3 4
5 6

Sample Output 2

10 10 10 10 10 10 20

Sample Input 3

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

Sample Output 3

1 0 0 1 0 1