P17426 [ICPC 2018 Xuzhou R] Rikka with Sorting Networks

Rikka 知道冒泡排序是一种简单而优美的算法，快速排序是一种复杂但高效的算法，希尔排序则是一种怪异却实用的算法。Rikka 对所有的排序算法都很感兴趣，她可以为 ICPC 竞赛想出任意多的新题目。 Rikka 讨厌那些不断用相同思路出题的人，她希望自己不会变成自己所讨厌的样子。尽管她已经出过几道与归并排序、插入排序等排序算法相关的题目，她决定向你展示最后一道关于排序算法的题，从而为这个系列画上永远的句号。 在这里，Rikka 引入了排序网络，并首先定义了比较器。对于一个由前 $n$ 个最小正整数构成的排列 $A$，记作 $a_1, a_2, \cdots, a_n$，一个比较器 $[u, v]$（$u \ne v$）会将 $A$ 中的第 $u$ 个元素和第 $v$ 个元素以非递减序排列。形式化地，一个比较器是一个映射 $[u, v]$，满足 * $[u, v](a_u) = \min(a_u, a_v)$；且 * $[u, v](a_v) = \max(a_u, a_v)$；且 * 对所有满足 $k \ne u$ 且 $k \ne v$ 的 $k$，有 $[u, v](a_k) = a_k$。 Rikka 将一个排序网络定义为一系列比较器的复合，并为你提供了一个由 $k$ 个顺序给出的比较器构成的排序网络。现在，Rikka 希望你能统计有多少个从 $1$ 到 $n$ 的排列，在经过给定的排序网络后会变成一个几乎有序的排列。她称一个从 $1$ 到 $n$ 的排列是几乎有序的，当且仅当其最长上升子序列的长度至少为 $(n - 1)$。

输入包含多组测试数据，第一行包含一个整数 $T$（$1 \le T \le 100$），表示测试数据的组数。 对于每组测试数据，第一行包含三个整数 $n$（$2 \le n \le 50$），表示排列的长度，$k$（$0 \le k \le 10$），表示比较器的数量，以及 $q$（$10^8 \le q \le 10^9$），一个用于输出的质数。 接下来 $k$ 行，第 $i$ 行包含两个整数 $u$ 和 $v$ $(1 \le u < v \le n)$，表示第 $i$ 个比较器 $[u, v]$。

对于每组测试数据，输出一行一个整数，表示满足条件的排列数对 $q$ 取模的结果。

翻译由 DeepSeek V4 Pro 完成