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, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

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