Tree

soda有一个 $n$个点$m$条边的图. 他开始玩游戏, 游戏共有$q$轮. 在每一轮, 他可以从图中随机选择一条边. 在$q$轮过后, 他把那些重复出现的边移除(只保留一条). 如果剩下来的边形成一棵树, 那么soda就赢了.

soda想要知道总共有多少种选择方案可以使得他赢得游戏. 由于答案可能很大, soda给出另一个整数$p$, 你只需要输出答案对$p$取模后的结果.

Note: 两种选择被视为不同当且仅当至少存在一轮游戏soda选了不同的边.

输入有多组数据. 第一行包含一个整数$T$表示测试数据的组数. 对于每组数据:

第一行有4个整数$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$). 接下来$m$行, 每行有两个整数$x$和$y$, 表示节点$x$和$y$之间有一条边$(1 \le x, y \le n, x \ne y)$. 保证没有重边, 没有自环.

对于每组数据, 输出答案对$p$取模的结果.

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