四元环计数

【题目描述】

给定一张由 $N$ 个顶点和 $M$ 条边组成的无向图。这张图不一定是简单图。 第 $i$ 条边为 $\lbrace u _ i, v _ i \rbrace$。

对每条边 $i$，求 $A _ i$：即无序的 $3$ 条边 $x$、$y$、$z$ 的组合数，使得这 $4$ 条边（$i,x,y,z$）构成的子图与 $C _ 4$（含 $4$ 条边的环）同构。

【输入】

$N$ $M$
$u _ 0$ $v _ 0$
$u _ 1$ $v _ 1$
$\vdots$
$u _ {M-1}$ $v _ {M-1}$

【输出】

$A _ 0$ $A _ 1$ $\cdots$ $A _ {M-1}$

【输入样例】

4 5
0 3
2 0
2 1
2 3
1 3

【输出样例】

1 1 1 0 1

【输入样例2】

4 7
0 1
0 1
0 1
0 3
0 3
1 2
2 3

【输出样例2】

2 2 2 3 3 6 6

【数据范围】

• $2 \le N \le 300000$
• $1 \le M \le 300000$
• $0 \le u _ i \lt N$
• $0 \le v _ i \lt N$
• $u _ i \neq v _ i$

【来源】

Library Checker（yosupo06） counting_c4