QUEST4 - Dungeon of Death


To reach the treasure, Jones has to pass through the "Room of Death". The floor of this room is a square with side 120 units. It is laid with square tiles of dimensions {1 X 1} arranged into a grid. But, at some places in the grid tiles are missing. As soon as the door to this room is opened poisonous gas starts coming out of these missing grid locations. The only escape from this gas is to completely cover these locations with planks lying outside the room. Each plank has dimensions {120 X 1} and can only be placed parallel to either sides of the floor. Now Jones wants to minimize the damage to his health so that he has enough of it left for the treasure. He figures out that in order to achieve this he has to use the minimum number of planks possible. He also realises that even if the planks overlap, poisonous gas from the missing tiles can still be successfully blocked. Please help Jones in this task.

Dungeon of Death: Tiles Uncovered
Dungeon of Death: Tiles Covered

Input

  • The first line of the input is a positive integer t <= 20, denoting the number of rooms.
  • The descriptions for the t rooms follow one after the other.
  • Room Description:
    • The first line of the room description is a positive integer n (n <= 10010), denoting the number of missing tile locations.
    • This is followed by the n lines, one for each missing tile location.
    • Each line contains two integers x y (0 <= x, y < 120), separated by a single space, representing the co-ordinates of the missing tile location.

Output

The output should consist of t lines, one for each room. The kth line in the output should be an integer mk, the minimum number of planks needed for the kth room.

Example

Input:
2
3
1 0
2 0
3 0
4
1 1
2 2
3 3
4 4

Output:
1
4


hide comments
joqsan_77: 2018-08-24 14:46:27

Nice problem.

Without looking at the tag, it's more natural to frame it as a min-cut problem and then apply the Min-Cut Max-Flow Theorem.

Last edit: 2018-08-24 15:02:35
foodman47: 2017-07-31 09:38:57

Last edit: 2017-07-31 09:51:35
npsabari: 2012-10-08 17:47:20

Why 8s??


Added by:Kashyap KBR
Date:2005-12-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET