Problem 673

Beds and Desks

At Euler University, each of the $n$ students (numbered from $1$ to $n$) occupies a bed in the dormitory and uses a desk in the classroom.

Some of the beds are in private rooms which a student occupies alone, while the others are in double rooms occupied by two students as roommates. Similarly, each desk is either a single desk for the sole use of one student, or a twin desk at which two students sit together as desk partners.

We represent the bed and desk sharing arrangements each by a list of pairs of student numbers. For example, with $n=4$, if $(2,3)$ represents the bed pairing and $(1,3)(2,4)$ the desk pairing, then students $2$ and $3$ are roommates while $1$ and $4$ have single rooms, and students $1$ and $3$ are desk partners, as are students $2$ and $4$.

The new chancellor of the university decides to change the organisation of beds and desks: a permutation $\sigma$ of the numbers $1,2,\ldots,n$ will be chosen, and each student $k$ will be given both the bed and the desk formerly occupied by student number $\sigma(k)$.

The students agree to this change, under the conditions that:

Any two students currently sharing a room will still be roommates.
Any two students currently sharing a desk will still be desk partners.

In the example above, there are only two ways to satisfy these conditions: either take no action ($\sigma$ is the identity permutation), or reverse the order of the students.

With $n=6$, for the bed pairing $(1,2)(3,4)(5,6)$ and the desk pairing $(3,6)(4,5)$, there are $8$ permutations which satisfy the conditions. One example is the mapping $(1, 2, 3, 4, 5, 6) \mapsto (1, 2, 5, 6, 3, 4)$.

With $n=36$, if we have bed pairing:
$(2,13)(4,30)(5,27)(6,16)(10,18)(12,35)(14,19)(15,20)(17,26)(21,32)(22,33)(24,34)(25,28)$
and desk pairing
$(1,35)(2,22)(3,36)(4,28)(5,25)(7,18)(9,23)(13,19)(14,33)(15,34)(20,24)(26,29)(27,30)$
then among the $36!$ possible permutations (including the identity permutation), $663552$ of them satisfy the conditions stipulated by the students.

The downloadable text files beds.txt and desks.txt contain pairings for $n=500$. Each pairing is written on its own line, with the student numbers of the two roommates (or desk partners) separated with a comma. For example, the desk pairing in the $n=4$ example above would be represented in this file format as:

1,3
2,4

With these pairings, find the number of permutations that satisfy the students’ conditions. Give your answer modulo $999,999,937$.

床位和座位

欧拉大学有$n$个学生（编号为$1$至$n$），每个学生在宿舍有一个床位，在教室里有一个座位。

这其中，某些床位是单人间，某些则是双人间；同样地，某些座位是单人桌，某些则是双人桌。

我们用一系列数对来表示床位和座位安排。例如，当$n=4$时，如果床位安排是$(2,3)$，而座位安排是$(1,3)(2,4)$，那就意味着$2$号和$3$号住的是双人间，而$1$号和$4$号住的是单人间，同时$1$号和$3$号、$2$号和$4$号分别共用一张双人桌。

新任校监打算调整一下床位和座位安排：他会选择$1,2,\ldots,n$的一个排列$\sigma$，然后$k$号学生会获得原本$\sigma(k)$号学生的床位和座位。

学生们表示，只有满足以下条件时，他们才愿意进行调整：

原本的室友在调整后仍然是室友。
原本的同桌在调整后仍然是同桌。

在之前的例子中，只有两种满足上述条件的排列：要么就什么都不做（此时选择的$\sigma$称为恒等排列 ），要么将学生们的编号逆序排列。

当$n=6$时，若当前的床位安排是$(1,2)(3,4)(5,6)$，当前的座位安排是$(3,6)(4,5)$，则共有$8$种排列符合要求，其中一种是$(1, 2, 3, 4, 5, 6) \mapsto (1, 2, 5, 6, 3, 4)$。

当$n=36$，若当前的床位安排是
$(2,13)(4,30)(5,27)(6,16)(10,18)(12,35)(14,19)(15,20)(17,26)(21,32)(22,33)(24,34)(25,28)$
而当前的座位安排是
$(1,35)(2,22)(3,36)(4,28)(5,25)(7,18)(9,23)(13,19)(14,33)(15,34)(20,24)(26,29)(27,30)$
那么在所有的$36!$种可能的排列中（包括恒等排列），共有$663552$种满足学生们的条件。

在文本文件beds.txt和desks.txt中，包含有一组$n=500$时的座位和床位安排。每一行描述了一组室友或同桌，用逗号分隔。举例来说，上述$n=4$的例子中的同桌关系在上述文件中会表示为

1,3
2,4

给定这些室友和同桌关系，求满足所有学生条件的排列总数，并将你的答案对$999,999,937$取余。