카피바라 코지 카니발

카피바라들이 카피바라 코지 카니발을 즐긴다. 의장 카피바라가 볼록한 케이크를 자른다. 케이크는 정 $n$각형이고 모서리는 $n$개다. 사용할 수 있는 색은 $k$가지다. 의장은 서로 교차하지 않는 대각선 모양의 절단선 $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$가 주어진다($1 \le u_i < v_i \le n$). 두 절단선이 같거나 끝점이 아닌 곳에서 만나는 경우는 없다. 모든 절단선은 직선이며 케이크 내부를 지난다. 모든 테스트 케이스의 $m$ 합은 $2 \cdot 10^5$을 넘지 않는다.

각 테스트 케이스마다 모서리를 칠하는 방법의 수를 $998\,244\,353$으로 나눈 나머지를 출력한다. 모든 색을 쓸 필요는 없다.

첫 번째 테스트 케이스에서 모서리 1은 3가지 색 중 하나다. 모서리 2는 남은 2가지 색 중 하나다. 모서리 3은 남은 색 하나이고, 모서리 4는 모서리 2와 같은 색이다. 따라서 총 6가지 방법이 있다. 두 번째 테스트 케이스에서는 모서리 수가 홀수이고 색은 2가지뿐인데, 이웃한 모서리가 모두 달라야 하므로 불가능하다.