All Tracks Problem

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: 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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

November Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?