회로 배선 연결

인쇄 회로 기판(PCB) 위의 디지털 논리 회로는 서로 연결된 여러 부품으로 이루어지며, 이 부품들은 보통 집적 회로(IC) 칩이다. 각 IC 칩에는 여러 개의 핀이 있고, 이 핀들은 전선으로 다른 칩의 핀이나 전원선에 연결되어야 한다. 대부분의 PCB는 여러 층을 쌓아 만든다. 각 층의 배선은 가로 방향과 세로 방향 전선으로 이루어진다. 여러 층으로 된 기판에서 층과 층은 비아(via)라고 부르는 뚫린 구멍으로 연결되며, 비아는 층 사이를 잇는 전도 경로가 된다.

복잡한 PCB를 설계할 때, 전원 공급만을 위한 특별한 층 하나를 둔다. 이 층은 다음 성질을 가진다.

1. 층의 맨 아래에는 가로 방향 전원선이 하나 놓인다.
2. 여러 개의 가로 전선이 미리 주어진다.
3. 층 위에는 비아가 여러 개 놓여 있다.
4. 모든 가로 전선은 세로 전선을 통해 전원선과 연결되어야 한다. 각 세로 전선은 전원선에서 출발해 위로 올라가면서 몇 개의 가로 전선과 만나 전력을 공급하고, 비아에서 끝난다.

비용을 줄이기 위해, 이 층에서 전원선에 연결되는 세로 전선의 개수를 최소로 하려고 한다.

비아 $(s, t)$ 에 놓인 세로 전선은 전원선에서 그 비아까지 이어진다. 따라서 이 세로 전선은 $q \le s \le r$ 이면서 $p < t$ 인 가로 전선 $(p, q, r)$ 에만 전력을 공급한다.

아래 그림 (a)에는 가로 전선 4개와 비아 7개가 있다. 이때 모든 가로 전선에 전력을 공급하는 데 필요한 세로 전선의 최소 개수는 3이다. 그림 (b)는 세로 전선 3개를 쓰는 한 가지 배치를 보여 준다. 한 가로 전선이 두 개 이상의 세로 전선과 만날 수도 있다.

(a)

(b)

가로 전선들과 비아들이 주어질 때, 전원선과 모든 가로 전선을 잇는 세로 전선의 최소 개수를 구하는 프로그램을 작성하라.

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $M$ 과 $N$ ($1 \le M, N \le 100$) 이 주어진다. $M$ 은 가로 전선의 개수, $N$ 은 비아의 개수이다.

이어지는 $M$ 개의 줄에는 각 가로 전선이 세 정수 $p$, $q$, $r$ 로 주어진다. $p$ ($1 \le p \le 10000$) 는 전선의 $y$ 좌표이고, $q$, $r$ ($1 \le q < r \le 10000$) 는 각각 왼쪽 끝과 오른쪽 끝의 $x$ 좌표이다. 어떤 두 가로 전선도 서로 만나지 않는다.

그다음 $N$ 개의 줄에는 각 비아가 두 정수 $s$, $t$ ($1 \le s, t \le 10000$) 로 주어진다. $s$ 와 $t$ 는 각각 비아의 $x$ 좌표와 $y$ 좌표이다. 같은 세로선 위에는 비아가 많아야 하나 있으며, 어떤 비아도 가로 전선 위에 놓여 있지 않다. 전원선은 $x$ 축 위에 있다.

각 테스트 케이스마다 한 줄에, 전원선과 모든 가로 전선을 잇는 세로 전선의 최소 개수를 출력한다. 모든 가로 전선을 세로 전선 하나 이상으로 연결할 수 없으면, 대신 IMPOSSIBLE 을 출력한다.