AT_pakencamp_2023_day2_e Is Either 1?

有 $N$ 张卡片，依次称为第 $1, 2, \cdots, N$ 张卡片。每张卡片的正反面分别写着 $0$ 和 $1$。 这些卡片需要按照 $M$ 个条件全部满足的方式，选择正面或反面朝上放在桌子上。第 $i$ 个条件如下，满足以下至少一项即可： - 第 $A_i$ 张卡片的正面朝上且写着 $X_i$。 - 第 $B_i$ 张卡片的正面朝上且写着 $Y_i$。 保证一定存在至少一种卡片摆放方式满足所有条件，可能有多种。请你计算满足以下所有条件的整数四元组 $(p, q, r, s)$ 的数量： - $1 \leq p, q \leq N$； - $\{r, s\} \subset \{0, 1\}$； - 对于所有满足条件的卡片摆放方式，以下至少一项成立： - 第 $p$ 张卡片正面朝上为 $r$。 - 第 $q$ 张卡片正面朝上为 $s$。

输入从标准输入读入，格式如下： > $N$ $M$ $A_1$ $B_1$ $X_1$ $Y_1$ $A_2$ $B_2$ $X_2$ $Y_2$ $\vdots$ $A_M$ $B_M$ $X_M$ $Y_M$

请输出一个整数，即答案。

### 输入输出样例 1 说明 需要保证第 $1$ 张或第 $2$ 张卡片的正面写着 $0$。满足条件的卡片正面朝上情况有 $ (0, 0), (1, 0), (0, 1) $ 共 $3$ 种。所以符合条件的 $(p, q, r, s)$ 有 $ (1, 1, 0, 1), (1, 1, 1, 0), (1, 2, 0, 0), (2, 1, 0, 0), (2, 2, 0, 1), (2, 2, 1, 0) $。 ### 数据范围 - $1 \leq N \leq 3 \times 10^4$ - $0 \leq M \leq 3 \times 10^4$ - $1 \leq A_i, B_i \leq N$ - $\{ X_i, Y_i \} \subset \{0, 1\}$ - 保证至少存在一种卡片摆放方式满足所有条件。 - 所有输入均为整数。 由 ChatGPT 5 翻译