Alice and rooks
Tag(s):

## Medium

Problem
Editorial
Analytics

Alice has a chess board with n rows and m columns. There are k obstacles on the board placed exactly in cells. Two different rooks form a bad pair if they stay in one row or in one column and there are no obstacles between them.

Alice want to know a maximal number of rooks which she can put on the board without bad pairs. Help her calculate this number.

You have to solve this problem for several test cases.

$INPUT$

The first line of the input contains a single integer $tests$ - a number of test cases.

Each test case is given in the following format:

The first line contains a three integers n, m and k ($1 \leq n, m \leq 500$, $0 \leq k < n \cdot m$) - a number of rows, a number of columns and a number of obstacles.

Then follow k lines with obstacles description. The i-th of these lines contains two integers $r_i$ and $c_i$ ($1 \leq r_i \leq n$, $1 \leq c_i \leq m$) - a row number of i-th obstacle and a column number of i-th obstacle.

Guaranteed that all obstacles are placed in the different cells.

Guaranteed that $\sum_{i=1}^{tests} n_i \cdot m_i \leq 250000$.

$OUTPUT$

For each test case print a single integer number - an answer of the problem.

SAMPLE INPUT
2
3 5 2
1 4
2 2
2 2 3
1 1
1 2
2 1

SAMPLE OUTPUT
5
1

Time Limit: 4.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

November Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs
• Data Structures > Advanced Data Structures
• Data Structures > Advanced Data Structures
• Algorithms > Searching