题目描述

Aliens have landed. These aliens find our Earth's rivers intriguing because their home planet has no flowing water at all, and now they want to construct their alien buildings in some of Earth's rivers. You have been tasked with making sure their buildings do not obstruct the flow of these rivers too much, which would cause serious problems. In particular, you need to determine what the maximum flow that the river can sustain is, given the placement of buildings.

The aliens prefer to construct their buildings on stretches of river that are straight and have uniform width. Thus you decide to model the river as a rectangular grid, where each cell has integer coordinates $(X, Y; 0 \leq X < W$ and $0 \leq Y < H)$. Each cell can sustain a flow of 1 unit through it, and the water can flow between edge-adjacent cells. All the cells on the south side of the river (that is with y-coordinate equal to 0) have an implicit incoming flow of 1. All buildings are rectangular and are grid-aligned. The cells that lie under a building cannot sustain any flow. Given these constraints, determine the maximum amount of flow that can reach the cells on the north side of the river (that is with y-coordinate equal to $H-1$).

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case will begin with a single line containing three integers, $W$, the width of the river, $H$, the height of the river, and $B$, the number of buildings being placed in the river. The next $B$ lines will each contain four integers, $X_0$, $Y_0$, $X_1$, and $Y_1$. $X_0$, $Y_0$ are the coordinates of the lower-left corner of the building, and $X_1$, $Y_1$ are the coordinates of the upper-right corner of the building. Buildings will not overlap, although two buildings can share an edge.

输出格式

For each test case, output one line containing "Case #$x$: $m$", where $x$ is the test case number (starting from 1) and $m$ is the maximum flow that can pass through the river.

2
3 3 2
2 0 2 0
0 2 0 2
5 6 4
1 0 1 0
3 1 3 3
0 2 1 3
1 5 2 5

Case #1: 1
Case #2: 2

提示

Sample Explanation

Here are visual representations of the two test cases in the sample input:

Limits

• $1 \leq T \leq 100$.
• $0 \leq X_0 \leq X_1 < W$.
• $0 \leq Y_0 \leq Y_1 < H$.

Small dataset(10 Pts)

• Time limit: 60 3 seconds.
• $3 \leq W \leq 100$.
• $3 \leq H \leq 500$.
• $0 \leq B \leq 10$.

Large dataset(20 Pts)

• Time limit: 120 5 seconds.
• $3 \leq W \leq 1000$.
• $3 \leq H \leq 10^8$.
• $0 \leq B \leq 1000$.