버스 노선의 연결된 정류장

문제

길게 뻗은 한 도로의 정류장에는 도로를 따라 1부터 1,000,000까지의 정수 번호가 붙어 있다. 버스 운영 담당자는 이 도로를 지나는 여러 노선의 운행 범위를 모아 안내판을 만들려고 한다. 한 노선의 운행 범위는 두 정수 L과 R로 주어지며, 이 노선은 번호가 L 이상 R 이하인 모든 정류장에 정차한다. L과 R이 같으면 해당 정류장 하나에만 정차하는 노선이다. 노선의 진행 방향이나 배차 간격은 이번 안내판에서 고려하지 않는다. 하나 이상의 노선이 정차하는 정류장을 운행 정류장이라고 한다. 여러 노선이 같은 정류장에 정차하더라도 그 정류장은 한 번만 센다. 운행 정류장을 번호 순으로 나열했을 때 번호가 연속하는 정류장들은 하나의 연결 구역을 이룬다. 각 연결 구역은 더 이상 양쪽으로 늘릴 수 없는 최대 범위여야 한다. 따라서 두 연결 구역 사이에는 반드시 운행 정류장이 아닌 정류장이 하나 이상 존재한다. 예를 들어 어떤 노선이 20번부터 23번까지 정차하고 다른 노선이 24번부터 26번까지 정차한다면, 20번부터 26번까지는 빠진 번호가 없으므로 하나의 연결 구역이다. 이때 두 노선이 공통으로 정차하는 정류장이 없어도 연결 구역은 나뉘지 않는다. 반면 운행 정류장이 20번부터 23번까지와 25번부터 26번까지뿐이라면 24번이 빠져 있으므로 두 구역이다. 주어진 노선의 입력 순서는 임의적이며, 같은 운행 범위가 여러 번 주어질 수도 있다. 모든 노선을 반영했을 때 연결 구역이 몇 개인지와 서로 다른 운행 정류장이 모두 몇 개인지 구한다. 노선은 적어도 하나 주어지므로 연결 구역과 운행 정류장은 항상 존재한다. 두 개수만 출력하며 구역의 위치나 노선의 순서는 출력하지 않는다.

입력

첫째 줄에 노선 수 N이 주어진다. N은 1 이상 20,000 이하의 정수다.
다음 N개 줄에 각 노선의 운행 범위를 나타내는 정수 L과 R이 공백으로 구분되어 주어진다. 1 ≤ L ≤ R ≤ 1,000,000이다.

출력

연결 구역의 수와 서로 다른 운행 정류장의 수를 이 순서대로 공백으로 구분하여 한 줄에 출력한다.

4
2 4
6 8
4 6
12 12

2 8

3
1 1
1 1
1 1

1 1

3
20 23
24 26
28 28

2 8

출처: Devin.KR 자체 제작