경쟁

영화관 맨 앞줄 좌석의 표를 판매하고 있다. 맨 앞줄에는 왼쪽에서 오른쪽으로 1부터 N까지 번호가 매겨진 N개의 좌석이 있다. 지난주 내내 사무실을 비웠다가 돌아와 보니 좌석 예약 Q건이 밀려 있었다! i번째 예약은 $L_{i}$부터 $R_{i}$까지의 모든 좌석을 요청한다. 이제 각 예약을 한 번에 하나씩 시스템에 입력하는 지루한 일을 해야 한다.

일부 예약은 서로 겹칠 수 있으므로 시스템이 각 예약을 전부 처리하지 못할 수도 있다. 예약을 시스템에 입력하면, 해당 예약이 요청한 좌석 중 앞서 시스템에 입력된 예약에 아직 배정되지 않은 모든 좌석을 그 예약에 배정한다.

각 예약에 적어도 k개의 좌석이 배정되도록 예약을 시스템에 입력할 수 있는 순서가 존재할 때, 가장 큰 정수 k는 무엇인가?

제한

시간 제한: 테스트 세트당 15초. 메모리 제한: 1GB. T = 100. 1 ≤ N ≤ $10^{6}$. 1 ≤ $L_{i}$ ≤ $R_{i}$ ≤ N.

테스트 세트 1 (공개)

1 ≤ Q ≤ 300.

테스트 세트 2 (비공개)

1 ≤ Q ≤ 30000. 테스트 케이스 중 적어도 85개에서는 Q ≤ 3000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 각각 좌석 수와 예약 수를 나타내는 두 정수 N과 Q가 포함된 한 줄로 시작한다. 그다음 Q개의 줄이 더 주어지며, 그중 i번째 줄에는 두 정수 $L_{i}$와 $R_{i}$가 주어진다. 이는 i번째 예약이 $L_{i}$부터 $R_{i}$까지의 모든 좌석을 예약하려 한다는 뜻이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 위에서 설명한 가장 큰 값 k이다.

예제 케이스 #1에는 N = 5개의 좌석과 Q = 3건의 예약이 있다. 가능한 순서 중 하나는 다음과 같다.

• 두 번째 예약을 입력하면 시스템이 2개의 좌석(3와 4)을 예약한다.

• 첫 번째 예약을 입력하면 시스템이 2개의 좌석(1와 2)을 예약한다.

• 세 번째 예약을 입력하면 시스템이 1개의 좌석(5번 좌석만 해당하며, 1, 2, 3, 4번 좌석은 이미 예약되어 있다)을 예약한다.

각 예약에는 적어도 1개의 좌석이 배정되며, 각 예약에 적어도 2개의 좌석을 배정하는 순서는 존재하지 않으므로 답은 1이다.

예제 케이스 #2에는 N = 30개의 좌석과 Q = 3건의 예약이 있다. 좌석을 어떤 순서로 배정하더라도 적어도 하나의 예약에는 좌석이 전혀 배정되지 않는다. 따라서 답은 0이다. 어떤 예약에도 포함되지 않는 좌석이 있을 수 있음에 유의하라!

예제 케이스 #3에는 N = 10개의 좌석과 Q = 4건의 예약이 있다. 가능한 순서 중 하나는 다음과 같다.

• 두 번째 예약을 입력하면 시스템이 2개의 좌석(4와 5)을 예약한다.

• 세 번째 예약을 입력하면 시스템이 2개의 좌석(3와 6, 4와 5은 이미 예약되어 있다)을 예약한다. 예약되는 좌석들이 반드시 서로 인접할 필요는 없음에 유의하라.

• 네 번째 예약을 입력하면 시스템이 2개의 좌석(2와 7)을 예약한다.

• 첫 번째 예약을 입력하면 시스템이 2개의 좌석(1와 8)을 예약한다.

각 예약에는 적어도 2개의 좌석이 배정되며, 각 예약에 적어도 3개의 좌석을 배정하는 순서는 존재하지 않으므로 답은 2이다.

참고: 이 문제의 대규모 데이터 세트에는 인터프리터 방식의 느린 언어를 사용하지 않는 것을 권장한다.