题目描述

有一块正 $n$ 边形蛋糕。蛋糕上进行了 $m$ 次互不相交的对角线切割，将蛋糕分成了 $m+1$ 块。

你需要使用 $k$ 种颜色给原正多边形的每个顶点染色，使得切割后每一块蛋糕上任意两个相邻顶点的颜色都不同。

两个顶点被认为相邻，当且仅当满足以下至少一个条件：

• 它们在原正多边形上相邻；
• 它们是一条切割线的两个端点。

不要求所有颜色都被使用。

请计算满足条件的染色方案数。答案对 $998\,244\,353$ 取模。

输入格式

每个输入包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数。

对于每组测试数据：

• 第一行包含三个整数 $n,m,k$，分别表示蛋糕的顶点数、切割数和可用颜色数；
• 接下来 $m$ 行，第 $i$ 行包含两个整数 $u_i,v_i$，表示第 $i$ 条切割连接顶点 $u_i$ 和 $v_i$。

任意两条切割线不会重合，也不会在端点之外相交。所有切割线都是严格经过蛋糕内部的直线段。

数据范围

所有测试数据的 $m$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每组测试数据，输出一个整数，表示合法染色方案数对 $998\,244\,353$ 取模后的结果。

样例

4
4 1 3
1 3
5 0 2
9 4 3
1 3
1 6
4 6
6 8
3 0 1001

6
0
54
1754647

样例说明

在第一组测试中，顶点 $1$ 有 $3$ 种颜色可选；顶点 $2$ 必须选择剩余两种颜色之一；顶点 $3$ 只能使用最后一种颜色；顶点 $4$ 与顶点 $2$ 同色。因此共有 $6$ 种方案。

在第二组测试中，顶点数为奇数且只有两种颜色，而每对相邻顶点都必须异色，因此不存在合法染色。