그리드랜드의 심술쟁이 마못

그리드랜드의 아름다운 숲에는 세상에서 가장 귀여운 마못 무리가 살고 있다. 유난히 더웠던 올여름, 마못들은 꽃피는 덤불에서 즐겁게 뛰어놀았고, 저마다 다른 마못들 사이에서 운명의 짝을 찾았다.

그런데 겨울이 왔고, 마못들은 모두 저마다의 굴로 돌아가 겨울을 난다. 물론 모두 심술이 나고 외롭기 짝이 없다. 이들은 운명의 짝과 다시 만나고 싶어 한다. 다행히 마못들은 지하 통로 굴착 연구 회사에 도움을 청했다. 회사의 대표로서, 당신의 임무는 사랑에 빠진 마못들이 서로를 정기적으로 방문할 수 있게 해 줄 터널망을 건설하는 것이다. 이 일을 해낸다면, 그리드랜드의 마못들이 얼마나 고마워할지 상상해 보라!

사전 조사 결과, 그리드랜드의 흙은 음이 아닌 정수 좌표 쌍으로 표시되는 정사각형 칸들로 이루어져 있다. 첫 번째 정수는 x축상의 위치, 즉 원점(가장 왼쪽 점)으로부터의 거리를 나타내고, 두 번째 정수는 깊이를 나타낸다. 각 마못은 깊이 0인 칸의 굴에 산다. 당신의 굴착 도구는 그리드랜드의 흙에서 깊이 1 이상인 임의의 칸을 비울 수 있다(굴 자체는 굴착할 필요가 없다). 그 결과를 터널망이라고 부른다. 터널망에서의 경로란 굴착된 칸들의 나열로서, 각 칸이 이전 칸과 가로 또는 세로로 인접한 것이다. 생물학자라면 누구나 말해 주겠지만, 그리드랜드의 마못은 너무 뚱뚱해서 대각선으로 인접한 두 칸 사이를 움직일 수 없다. 터널망은 모든 마못 커플에 대해, 그 커플의 두 굴을 잇는 굴착된 칸들의 경로가 존재하도록 해야 한다. 그러나 마못들의 사생활을 지키기 위해, 커플이 아닌 두 마못의 굴을 잇는 경로는 절대 있어서는 안 된다.

당신의 일은 두 가지 질문을 해결하는 것이다. 첫째, 이러한 조건을 만족하는 터널망을 만드는 것이 과연 가능한가? 둘째, 가능하다면, 파야 하는 최대 깊이는 얼마인가?

입력은 여러 테스트 케이스로 이루어진다. 첫 줄에는 테스트 케이스의 수를 나타내는 정수가 주어진다. 각 테스트 케이스가 이어진다. 테스트 케이스의 첫 줄에는 마못 커플의 수를 나타내는 양의 정수 N이 주어지며, 1 ≤ N ≤ 10^6이다. 이어서 N개의 줄에 각 커플이 주어진다. 각 줄에는 단일 공백으로 구분된 두 양의 정수 0 ≤ a_i < b_i ≤ 10^9가 주어지며, 이는 커플의 첫 번째와 두 번째 구성원의 굴 위치를 나타낸다(왼쪽에 있는 것부터 시작한다). 같은 굴에 사는 마못은 없고, 인접한 굴도 없다(즉, 임의의 두 굴 위치의 차의 절댓값은 2 이상이다).

입력의 각 테스트 케이스에 대해 프로그램은 한 줄을 출력해야 한다. 조건을 만족하는 터널망이 없으면 그 줄의 내용은 IMPOSSIBLE이어야 한다. 그렇지 않으면 그 줄의 내용은 양의 정수 d > 0이어야 하며, 이는 조건을 만족하고 모든 굴착된 칸의 깊이가 d 이하인 터널망이 존재하는 가장 작은 깊이이다. 출력에 빈 줄이 있어서는 안 된다.

그림 3의 왼쪽 다이어그램에는 네 쌍의 마못이 있고, 각 커플 구성원의 굴은 A, B, C, D로 표시되어 있다. 이 다이어그램은 깊이 5의 터널망을 보여 주며, 굴착된 칸은 빗금으로 표시되어 있다. 실제로 이 예에서 적합한 터널망의 최소 최대 깊이는 5이다.

물론 적합한 터널망이 전혀 존재하지 않을 수도 있다! 예를 들어 그림 3의 오른쪽 다이어그램에는 두 쌍의 마못 A와 B가 있다. 커플 구성원을 서로 교차하지 않는 터널로 연결하는 것은 불가능하므로, 불쌍한 마못들은 겨울 내내 심술을 부리며 지낼 것이다!

그림 3: 샘플 입력의 처음 두 입력에 대한 그림