간척왕 우만금

문제 정보

문제

세계는 지금 기후변화로 인한 위기에 직면해 있습니다. 특히 해수면 상승 문제는 몇몇 국가와 도시들에 큰 위협이 되고 있는데요. 최근 국토가 점점 늘어나고 있는 섬나라가 있어 화제를 모으고 있습니다.

이 나라의 통치자 우만금은 간척왕이라는 별명으로 유명합니다. 간척왕 우만금은 매년 엄청난 예산을 들여 간척사업을 진행하고 있어, 몇 년 후면 이 나라의 모든 섬이 하나가 돼 대륙의 기상을 뽐낼 기세인데요....... 그게 과연 몇 년 후일까요?

이 나라의 지도가 격자 상에 주어집니다. 격자의 각 칸은 육지거나 바다입니다. 이 때 두 개 이 상의 육지가 상하좌우 혹은 대각선으로 맞닿아 있을 경우 이들은 하나의 섬을 이룹니다. 그런데 현재 지도 상의 섬은 육지가 전부 상하좌우로 연결되어 있고, 대각선으로 맞닿아 있는 경우는 없습니다. 그래서 입력으로 주어지는 섬은 격자 선 상의 수직/수평 선분으로 연결된 하나의 직각다각형으로 표현됩니다. 이 나라에서는 매년 간척 사업을 통해 섬과 상하좌우 혹은 대각선으로 맞닿아 있는 바다를 육지로 바꿉니다. 현재 상태부터 시작해 모든 섬이 하나의 섬으로 연결될 때까지 몇 년이 걸릴지 계산하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C가 주어집니다. 각 테스트 케이스의 첫 줄에는 지도 상의 섬의 수 N이 주어집니다. 그 후 N줄에 각 섬의 꼭지점 수 P와 P개의 꼭지점 좌표 Xi, Yi가 주어집니다. 이 꼭지점들을 순서대로 연결하면 섬의 외곽선이 되고, 내부 격자 칸이 전부 육지가 됩니다. 섬을 이루는 외곽선은 서로 교차하지 않고, 모든 꼭지점에서는 하나의 수직 선분과 하나의 수평 선분이 만납니다. 어떤 두 섬도 상하좌우 혹은 대각선으로 맞닿아 있지 않습니다.

출력

각 테스트 케이스마다 한 줄에 모든 섬이 하나의 섬으로 연결될 때까지 걸리는 햇수를 출력하세요.

예제 입력

2
2
4 0 0 2 0 2 2 0 2
4 4 4 4 5 5 5 5 4
3
4 0 0 1 0 1 2 0 2
4 3 2 4 2 4 3 3 3
4 8 0 9 0 9 1 8 1

예제 출력

1
2

노트

2 ≤ N ≤ 50
4 ≤ P ≤ 50
0 ≤ Xi, Yi ≤ 1000000

2개의 댓글이 있습니다.