P12107 [NWRRC2024] Capybara Cozy Carnival

悠闲的水豚们正在庆祝水豚温馨嘉年华。水豚主席正在切分一块凸形蛋糕。这块蛋糕有 $n$ 个彩色顶点，使用无数种颜色中的 $k$ 种可选颜色。主席通过制作 $m$ 条连续且不相交的顶点间切分线，将蛋糕分成 $m + 1$ 块分发给同伴们。有趣的是，相邻蛋糕块的顶点必须使用对比色。 请计算满足切分条件的蛋糕顶点着色方案数。 换句话说，给定一个正 $n$ 边形的蛋糕和 $m$ 条不相交的对角线切分，这些切分将蛋糕分成 $m + 1$ 个切片。 计算将原始蛋糕每个顶点用 $k$ 种颜色之一着色的方案数，要求最终切片中任何相邻顶点颜色不同。两个顶点被认为是相邻的，如果它们在原始蛋糕中是连续的，或者是同一条切分线的端点。不需要使用所有颜色。由于方案数可能很大，请输出其对 $998\,244\,353$ 取模的结果。

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各测试用例的描述。 每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$，分别表示蛋糕顶点数、切分线数和可用颜色数（$3 \le n \le 10^9$；$0 \le m \le 2\cdot 10^5$；$2 \le k \le 10^6$）。 接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$，表示第 $i$ 条切分线连接的两个顶点（$1 \le u_i < v_i \le n$）。任意两条切分线不能重合或相交（端点除外），所有切分线都严格位于蛋糕内部。 保证所有测试用例的 $m$ 之和不超过 $2\cdot 10^5$。

对于每个测试用例，输出满足相邻顶点颜色不同的着色方案数，对 $998\,244\,353$ 取模。注意不需要使用所有颜色。

在第一个测试用例中，顶点 $1$ 有 $3$ 种颜色可选，顶点 $2$ 有 $2$ 种剩余颜色可选，顶点 $3$ 使用最后一种颜色，顶点 $4$ 必须与顶点 $2$ 同色。因此共有 $6$ 种方案。 在第二个测试用例中，顶点数为奇数且只有两种颜色，要求每对连续顶点颜色不同，这是不可能的。