← 返回题目列表

AtCoder · arc083_d

F. 收集球

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

分数: 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.