405619: GYM102012 I Rikka with Sorting Networks

Rikka knows that Bubble sort is a simple but beautiful algorithm, Quicksort is a complex but efficient algorithm, and Shellsort is a weird but practical algorithm. Rikka is interested in all sorting algorithms and she can assign as many new problems for ICPC contests as she wants.

Rikka hates those guys who create new problems with the same ideas over and over again, and she hopes not to become the person she hates to be. Though she has already assigned several problems for sorting algorithms such as Merge sort and Insertion sort, she decides to show you the last problem about sorting algorithms to end this series forever.

Here Rikka introduces the sorting network and she defines a comparator at first. For a permutation $$$A$$$ of the $$$n$$$ smallest positive integers denoted by $$$a_1, a_2, \cdots, a_n$$$, a comparator $$$[u, v]$$$ ($$$u \ne v$$$) sorts the $$$u$$$-th and the $$$v$$$-th element in $$$A$$$ into nondecreasing order. Formally, a comparator is a mapping $$$[u, v]$$$ satisfying

• $$$[u, v](a_u) = \min(a_u, a_v)$$$; and
• $$$[u, v](a_v) = \max(a_u, a_v)$$$; and
• $$$[u, v](a_k) = a_k$$$ for all $$$k$$$ with $$$k \ne u$$$ and $$$k \ne v$$$.

Rikka defines a sorting network as a composition of comparators and provides for you a sorting network with $$$k$$$ ordered comparators. Now, Rikka wants you to count the number of permutations of $$$1$$$ to $$$n$$$ which, through the given sorting network, would become an almost sorted permutation. She says a permutation of $$$1$$$ to $$$n$$$ is almost sorted if the length of its longest increasing subsequence is at least $$$(n - 1)$$$.

The input contains several test cases, and the first line contains a single integer $$$T$$$ ($$$1 \le T \le 100$$$), the number of test cases.

For each test case, the first line contains three integers $$$n$$$ ($$$2 \le n \le 50$$$), the length of permutations, $$$k$$$ ($$$0 \le k \le 10$$$), the number of comparators, and $$$q$$$ ($$$10^8 \le q \le 10^9$$$), a prime number for the output.

Then $$$k$$$ lines follow, the $$$i$$$-th line of which contains two integers $$$u$$$ and $$$v$$$ $$$(1 \le u < v \le n)$$$, representing the $$$i$$$-th comparator $$$[u, v]$$$.

For each test case, output a single line with a single integer, the remainder of the number of permutations which meet the requirement divided by $$$q$$$.

4
4 0 998244353
4 1 998244353
1 2
4 3 998244353
1 2
2 3
1 2
4 6 998244353
1 2
2 3
1 2
3 4
2 3
1 2

10
14
24
24