← 返回题目列表

Codeforces · 859/E

E. 办公桌混乱

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

一套新桌子刚刚到货,是时候了!办公室里的东西变得相当拥挤。您负责为工程师创建新的座位表。办公桌已编号,您向工程团队发送了一份调查问卷,询问每位工程师他们当前坐在的办公桌编号,以及他们想要坐在的办公桌编号(可能与他们当前的办公桌相同)。每个工程师必须留在原来的位置,或者移动到他们在调查中指定的所需座位。目前,没有两名工程师坐在同一张桌子上,在新的座位安排中,也不可能有两名工程师坐在同一张桌子上。

您可以创建多少个满足指定要求的座位安排?答案可能非常大,因此请以 1000000007 = 109 + 7 为模进行计算。

输入

输入将以包含工程师人数 N (1 ≤ N ≤ 100000) 的行开始。

接下来是 N 行,每行恰好包含两个整数。第i行包含第i个工程师当前的办公桌号和第i个工程师想要移动到的办公桌号。桌子的编号为 1 到 2·N。保证没有两个工程师坐在同一张桌子上。

输出

打印可能的分配数,模 1000000007 = 109 + 7。

示例

输入 #1

4
1 5
5 2
3 7
7 3

输出 #1

6

输入 #2

5
1 10
2 10
3 10
4 10
5 5

输出 #2

5

注意

这些是第一个示例的可能分配:

- 1 5 3 7
- 1 2 3 7
- 5 2 3 7
- 1 5 7 3
- 1 2 7 3
- 5 2 7 3