영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
(그림은 원문 저장소에서 볼 수 있습니다)
Sample 1: turning on the two lighthouses with rays also lights the ones the arrows point to, so 4 lighthouses are lit.
We have a square grid consisting of n × n cells. There are m lighthouses placed on the grid. Initially, all lighthouses are “off”, but when you turn one on, all other lighthouses sharing the same x or y coordinate with the already lit lighthouse will also turn on, and this continues recursively. You can turn on k lighthouses, and because you hate darkness, your goal is to light as many lighthouses as possible by the end. How many lighthouses can you get to light up?
Input
The first line of input contains the integers n, m and k (1 ≤ n ≤ 3 · 10^5, 1 ≤ m ≤ 5 · 10^5, 1 ≤ k ≤ m).
The following m lines each contain the integer coordinates (x_i, y_i) for each lighthouse, satisfying 0 ≤ x_i, y_i < n. There is at most one lighthouse per cell. You may not assume that the lighthouses are uniformly distributed.
Output
Print an integer: the maximum number of lighthouses you can light up if you turn on at most k of them.
Scoring
Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 10 | m ≤ 2000 |
| 2 | 30 | m ≤ 30000 |
| 3 | 60 | No additional constraints. |
예제
예제 1
4 5 2 0 0 1 1 0 1 2 2 3 3
4
예제 2
20 15 4 19 2 6 15 18 6 18 11 0 10 9 12 17 8 14 2 17 10 3 9 12 11 5 19 0 4 13 11 1 5
11