Problem 3791 --Lawn of the Dead

3791: Lawn of the Dead

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $128$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

One day, a zombie came to the Lawn of the Dead, which can be seen as an n×m grid. Initially, he stood on the top-left cell, which is (1,1).
Because the brain of the zombie was broken, he didn't have a good sense of direction. He could only move down from (i,j) to (i+1,j) or right from (i,j) to (i,j+1)in one step.
There were k "lotato mines" on the grid. The i-th mine was at (xi,yi). In case of being destroyed, he would never step into a cell containing a "lotato mine".
So how many cells could he possibly reach? (Including the starting cell)

Input

The first line contains a single integer t (1≤t≤20), denoting the number of test cases.

The first line of each test case contains three integers n,m,k (2≤n,m,k≤105) --- there was an n×m grid, and there were k "lotato mines" on the grid.

Each of the following k lines contains 2 integers xi,yi (1≤xi≤n,1≤yi≤m) --- there was a "lotato mine" at (xi,yi). It's guaranteed that there was no "lotato mine" at (1,1) and no mines were in the same cell.

It is guaranteed that ∑n≤7⋅105,∑m≤7⋅105.

Output

For each test case, output the number of cells he could possibly reach.

Sample Input复制

1
4 4 4
1 3
3 4
3 2
4 3

Sample Output复制

10

提示

The cells that the zombie might reach are (1,1), (1,2), (2,1), (2,2), (2,3), (2,4), (3,1), (3,3), (4,1), (4,2).

推荐代码 查看3791 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛