Kotlin Heroes: Episode 7 |
---|
Finished |
There is an infinite chessboard, divided into cells. The cell $$$(x, y)$$$ is the cell on the intersection of the $$$x_i$$$-th row and $$$y_i$$$-th column. $$$n$$$ black pawns are placed on the board, the $$$i$$$-th black pawn occupies the cell $$$(x_i, y_i)$$$.
You want to capture all black pawns. In order to do so, you may perform the following actions:
Recall that when you make a move with a white pawn in the cell $$$(x, y)$$$, the chess rules allow you to choose exactly one of these actions:
You may perform any finite sequence of actions (placing white pawns and moving them). You want to capture all of the black pawns, and it can be shown that it is always possible; and you want to do it placing as few white pawns as possible.
What is the minimum number of white pawns you have to place to capture all $$$n$$$ black pawns?
The first line contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of black pawns.
Then $$$n$$$ lines follow. The $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le 5 \cdot 10^5$$$) denoting a black pawn in the cell $$$(x_i, y_i)$$$. No cell is occupied by two or more black pawns.
Print one integer — the minimum number of white pawns you have to place to capture all $$$n$$$ black pawns.
3 1 1 5 1 2 2
1
3 3 2 1 3 1 1
2
2 1 1 2 2
1
Name |
---|