← 返回题目列表

AtCoder · pakencamp_2023_day2_e

E. 是 1 吗?

中文机器翻译题面 查看原题

配点 : 700 点

問題文

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 。

制約

  • 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\}
  • 放置符合条件的卡牌的最佳方式是 1 存在。
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

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

2 1
1 2 0 0

出力例 1

6

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) 。


入力例 2

10 20
4 10 1 1
7 3 0 1
6 4 1 1
8 1 1 1
7 5 0 0
2 8 0 0
1 6 1 1
2 2 1 0
4 8 0 0
3 3 1 1
9 6 0 1
9 2 0 1
5 2 1 0
5 7 1 1
2 2 1 1
5 6 1 0
2 10 1 1
5 2 1 1
7 7 1 0
10 5 1 0

出力例 2

241