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 $σ$ of the numbers $1, 2, \dots, n$ will be chosen, and each student $k$ will be given both the bed and the desk formerly occupied by student number $σ (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 ( $σ$ 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, \dots, n$ 的一个排列 $σ$ ，然后 $k$ 号学生会获得原本 $σ (k)$ 号学生的床位和座位。

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

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

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

当 $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$ 取余。