计数 $C_4$（Counting $C_4$'s）

问题描述

给定一个无向图（可能含重边，但无自环），含 $N$ 个顶点和 $M$ 条边。第 $i$ 条边为 $\{u_i, v_i\}$。

对每条边 $i$，求 $A_i$：即满足以下条件的无序三元组 $\{x, y, z\}$ 的数量：

• $x, y, z$ 是三条边（索引）；
• 边 $i, x, y, z$ 共同构成一个与 $C_4$（4-环）同构的子图。

注：$C_4$ 是一个长度为 4 的简单环（4 个顶点、4 条边），因此这 4 条边必须恰好形成一个 4-环，且无额外边或重复顶点。

约束条件

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq M \leq 3 \times 10^5$
• $0 \leq u_i, v_i < N$
• $u_i \ne v_i$

输入

$N\ M$
$u_0\ v_0$
$u_1\ v_1$
:
$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 0 1 1 0

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

2 2 2 3 3 6 6