루미 알고리즘

#1304플래티넘Lighthouses

PO 2012 결선코딩영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPointsConstraints
110m ≤ 2000
230m ≤ 30000
360No 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

출처 표기

출처: Programmeringsolympiaden 2012년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.