Tree

soda has an undirected graph with $n$ vertices and $m$ edges. He is playing a game with $q$ rounds. In each round, he randomly chooses an edge from the graph. After $q$ rounds, he removes the duplicated edges. If the remaining edges form a tree, soda wins the game.

soda wants to know the number of different ways to choose edge in each round that will make him win the game.

As the answer will be very large, soda gives you another integer $p$. You should print the answer modulo $p$.

Note that two ways are considered different if at least in one round soda chooses different edges.

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains four integers $n, m, p, q$ $(2 \le n \le 100, 1 \le m \le \frac{n(n-1)}{2}, 1 \le p, q \le 10^9)$. Each of the following $m$ lines contains a pair of integers $x$ and $y$, that show that an edge exists between vertices $x$ and $y(1 \le x, y \le n, x \ne y)$. For each pair of vertices there will be at most one edge between them, no edge connects a vertex to itself.

For each test case, print the answer modulo $p$ in a single line.

2
6 6 23 10
6 3
6 4
5 1
2 5
1 4
5 4
6 5 23 5
5 6
4 6
3 1
5 1
1 2

16
5

BestCoder Round #58 (div.1)