All submissions for this problem are available.
Read problems statements in Mandarin Chinese here
City of Byteland can be described as a 2D grid of cells. Each cell may or may not contain a demon. You are given the list of cells that contain demons.
In a single Kamehameha attack, Goku can kill all the demons stading in a row or in a column. But using Kamehameha drains Goku's power. You are to tell the minimum number of Kamehameha attacks that will be required by Goku to destroy all the demons.
The first line contains T the number of test cases. The first line of each test case contains N the number of cells where enemies are present. The following N lines contain two integers X and Y each describing the index of the cell in which the demon is present.
For each case print the minimum number of attacks that are needed to kill all the monsters.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 1000
- 1 ≤ X, Y ≤ 109
Input 1 3 0 0 1 0 0 1 Output 2
|Tags||bipartite, easy-medium, kaushik_iska, matching, oct13|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.