Cross Coloring

题意翻译

题面: 有一张 $n$ 行 $m$ 列的网格,每一个网格里面都有一个细胞,所有细胞最初都是白色的 将进行 $q$次操作: 给定 $x_i,y_i$ - 从 $k$ 种非白色的颜色中选择一种给整个行 $x_i$和整个列 $y_i$ 上色 在里面。新的颜色将应用于每个单元格，无论该单元格在操作之前是否被着色。 应用所有 $q$ 操作称为着色。如果至少有一个细胞有不同的颜色，那么两种颜色是不同的。 有多少种不同的颜色?结果对998244353取模． 输入: 有多组测试数据,第一行有一个整数 $t$($1≤t≤10000$),表示测试数据的数量 第二行给定四个整数 $n,m,k,q$ ($1≤n,m,k,q≤2⋅10^5$),表示方格的长,宽,非白色的颜色的种类,操作次数 往后 $q$ 行 每行两个整数 x_i,y_i,表示第i次操作的行数和列数($1≤x_i≤n; 1≤y_i≤m$) 输出: 不同颜色的数量

题目描述

There is a sheet of paper that can be represented with a grid of size $ n \times m $ : $ n $ rows and $ m $ columns of cells. All cells are colored in white initially. $ q $ operations have been applied to the sheet. The $ i $ -th of them can be described as follows: - $ x_i $ $ y_i $ — choose one of $ k $ non-white colors and color the entire row $ x_i $ and the entire column $ y_i $ in it. The new color is applied to each cell, regardless of whether the cell was colored before the operation. The sheet after applying all $ q $ operations is called a coloring. Two colorings are different if there exists at least one cell that is colored in different colors. How many different colorings are there? Print the number modulo $ 998\,244\,353 $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of the testcase contains four integers $ n, m, k $ and $ q $ ( $ 1 \le n, m, k, q \le 2 \cdot 10^5 $ ) — the size of the sheet, the number of non-white colors and the number of operations. The $ i $ -th of the following $ q $ lines contains a description of the $ i $ -th operation — two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i \le n $ ; $ 1 \le y_i \le m $ ) — the row and the column the operation is applied to. The sum of $ q $ over all testcases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each testcase, print a single integer — the number of different colorings modulo $ 998\,244\,353 $ .

输入输出样例

输入样例 #1

2
1 1 3 2
1 1
1 1
2 2 2 3
2 1
1 1
2 2

输出样例 #1

3
4