分数: 1200 点
问题陈述
有 2N 球在 xy- 平面。的坐标 i- 其中第一个是 (x_i, y_i)。 在这里, x_i 和 y_i 是介于 1 和 N (含)适用于所有人 i,并且没有两个球占据相同的坐标。 B 型
为了收集这些球,Snuke 准备了 2N 机器人, A 型的 N 和 B 型 N 。 然后,他将A型机器人放置在坐标上 (1, 0), (2, 0), ..., (N, 0),以及坐标处的 B 型机器人 (0, 1), (0, 2), ..., (0, N),每个位置一个。
激活后,每种类型的机器人将按如下方式操作。
-
当 A 型机器人在坐标处激活时 (a, 0),它会移动到最低的球的位置 y- 线上球之间的坐标 x = a,收集球并使其自身停用。如果没有这样的球,它只会自行停用而不做任何事情。
-
当 B 型机器人在坐标处激活时 (0, b),它会移动到最低的球的位置 x- 线上球之间的坐标 y = b,收集球并使其自身停用。如果没有这样的球,它只会自行停用而不做任何事情。
一旦停用,机器人将无法再次激活。此外,当机器人正在操作时,在操作中的机器人被停用之前,不能激活新的机器人。
当 Snuke 准备启动机器人时,他注意到他可能无法收集到所有球,具体取决于启动机器人的顺序。
其中 (2N)! 激活机器人的可能顺序,找到可以收集所有球的数量,模 1 000 000 007.
约束
- 2 \leq N \leq 10^5
- 1 \leq x_i \leq N
- 1 \leq y_i \leq N
- If i ≠ j,或者 x_i ≠ x_j or y_i ≠ y_j.
输入
输入由标准输入按以下格式给出:
N
x_1 y_1
...
x_{2N} y_{2N}
输出
打印激活机器人的命令数量,以便可以收集所有球,模数 1 000 000 007.
示例输入 1
2 1 1 1 2 2 1 2 2
示例输出 1
8
我们将参考放置在 (1, 0) 和 (2, 0) 分别为A1和A2,机器人放置在 (0, 1) 和 (0, 2) 分别为 B1 和 B2。 满足条件的激活顺序有八种,如下:
- A1、B1、A2、B2
- A1、B1、B2、A2
- A1、B2、B1、A2
- A2、B1、A1、B2
- B1、A1、B2、A2
- B1、A1、A2、B2
- B1、A2、A1、B2
- B2、A1、B1、A2
因此,输出应该是 8.
示例输入 2
4 3 2 1 2 4 1 4 2 2 2 4 4 2 1 1 3
示例输出 2
7392
示例输入 3
4 1 1 2 2 3 3 4 4 1 2 2 1 3 4 4 3
示例输出 3
4480
示例输入 4
8 6 2 5 1 6 8 7 8 6 5 5 7 4 3 1 4 7 6 8 3 2 8 3 6 3 2 8 5 1 5 5 8
示例输出 4
82060779
示例输入 5
3 1 1 1 2 1 3 2 1 2 2 2 3
示例输出 5
0
当没有满足条件的激活顺序时,输出应该是 0.