#ABC213C. 卡牌重编号
卡牌重编号
AT_abc213_c [ABC213C] Reorder Cards
题目描述
有一个 行 列的网格,每个格子中放着一张卡片,因此共有 张卡片。其中只有 张卡片写了数字:对于 ,从上往下数第 行、从左往右数第 列的卡片上写有数字 ,其余 张卡片上什么都没有写。
接下来重复执行下面两种操作,直到两种操作都无法执行:
若存在一整行都没有写数字的卡片,则删去这一行,并把下方的卡片整体向上平移,使网格不留空隙;
若存在一整列都没有写数字的卡片,则删去这一列,并把右侧的卡片整体向左平移,使网格不留空隙。
每一步可以任选一种当前可执行的操作进行,执行次数不限。可以证明,无论以什么顺序执行这些操作,最终每张写了数字的卡片所在的位置都是唯一确定的。
请求出操作结束后,每张写了数字的卡片所在的行号和列号。
输入格式
第一行输入三个整数 $h, w, n \left(1 \leqq h, w \leqq 10^9;\ 1 \leqq n \leqq \min\left(10^5, h \times w\right)\right)$ 分别代表网格的行数、列数和写了数字的卡片数量。
此后 行,第 行输入两个整数 $a_i, b_i \left(1 \leqq a_i \leqq h;\ 1 \leqq b_i \leqq w\right)$ 代表写有数字 的卡片位于从上往下数第 行、从左往右数第 列。
保证所有 两两不同。
输出格式
输出 行。第 行输出两个整数 ,相邻两个整数之间用一个空格隔开,代表操作结束后写有数字 的卡片位于从上往下数第 行、从左往右数第 列。
测试样例
4 5 2
3 2
2 5
2 1
1 2
样例 1 解释
初始时写有数字 的卡片位于第 行第 列,写有数字 的卡片位于第 行第 列。
含卡片的行只有第 行和第 行,删去其余空行后,原第 行成为新第 行,原第 行成为新第 行;
含卡片的列只有第 列和第 列,删去其余空列后,原第 列成为新第 列,原第 列成为新第 列。
因此写有数字 的卡片最终位于第 行第 列,写有数字 的卡片最终位于第 行第 列,与输出一致。
1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10