울타리 칠하기

울타리를 칠할 사람들을 고용해야 한다. 울타리는 서로 이어진 10000개의 구간으로 구성되며, 각 구간에는 1부터 10000까지 번호가 매겨져 있다.

화가들로부터 울타리 칠하기를 돕겠다는 제안을 받는다. 각 화가는 연속된 울타리 구간의 부분집합을 특정 색으로 칠하겠다고 제안한다. 다음 조건을 만족하도록 제안들의 집합을 수락해야 한다:

• 울타리의 각 구간이 칠해진다.

• 울타리를 칠하는 데 최대 3개의 색을 사용한다.

이 두 요구 사항을 만족할 수 있다면, 수락해야 하는 제안의 최소 개수를 구한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 50

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 10

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 300

• 입력 파일의 테스트 케이스 수인 정수 T가 한 줄에 주어진다.

각 테스트 케이스에는 다음이 주어진다:

• 제안의 수인 정수 N이 한 줄에 주어진다.

• 각 제안에 대응하는 N개의 줄이 주어지며, 각 줄에는 "C A B"가 주어진다. 여기서 C는 색을 나타내는 최대 10개의 대문자로 이루어진 문자열이고, A는 칠할 첫 구간이며 B는 칠할 마지막 구간이다. 1 ≤ A ≤ B ≤ 10000.

• 입력 파일에 등장하는 순서대로 각 테스트 케이스에 대응하는 T개의 줄을 출력한다. 각 줄에는 문자열 "Case #X: Y"를 출력한다. 여기서 X는 테스트 케이스 번호이고, Y는 수락해야 하는 제안의 수이며, 수락 가능한 제안의 집합이 없다면 "Case #X: IMPOSSIBLE"를 출력한다.

첫 번째 테스트 케이스에서는 두 제안을 모두 수락하면 겹치는 부분 없이 각각 5000개 구간을 칠해 울타리 전체를 정확히 칠하게 된다.

두 번째 테스트 케이스에서는 화가들이 칠하는 구간이 겹치며, 이는 허용된다.

세 번째 테스트 케이스에서는 네 제안을 모두 수락하면 울타리 전체를 덮지만, 서로 다른 색을 4개 사용하므로 허용되지 않는다.

네 번째 테스트 케이스에서는 4001번 구간을 칠할 수 없다.

다섯 번째 테스트 케이스에서는 첫 번째와 두 번째 제안만 수락해도 울타리를 성공적으로 칠할 수 있다.