지도 인터페이스

많은 대중교통 시스템은 원하는 경로를 찾을 수 있는 온라인 인터페이스를 제공한다. 좋은 사용자 인터페이스 설계의 한 가지 원칙은 필요한 정보만 정확히 보여 주어 사용자가 중요한 부분에 집중할 수 있게 하는 것이다. 노선도를 그래픽으로 보여 줄 때 이는 곧, 지나가는 모든 역을 담되 그 외의 역은 되도록 적게 담은 지도를 보여 주는 것을 뜻한다. 한편 대부분의 사용자는 축척이 일정한 직사각형 지도에 익숙하므로, 여기서도 직사각형 지도만 사용한다.

문제를 구체적으로 정리하면 다음과 같다. 시스템에 있는 모든 역의 위치가 $(x, y)$ 좌표로 주어지고, 당신의 노선이 지나가는 역들의 목록이 순서대로 주어진다. 당신의 여정 전체를 포함하는, 변이 좌표축과 나란한 가장 작은 직사각형 안에 총 몇 개의 역이 들어가는지 구하여라. 직사각형의 경계선 위에 있는 역도 안에 있는 것으로 센다.

첫째 줄에 데이터 집합의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

• 각 데이터 집합의 첫째 줄에는 두 정수 $n$과 $m$이 주어진다. $n$은 시스템 전체의 역 수로 $2 \le n \le 500$이며, $m$은 여정이 지나가는 역의 수로 $2 \le m \le n$이다.
• 다음 $n$개의 줄에는 각각 두 정수 $x_i$ $y_i$가 주어지며, 이는 $i$번째 역의 좌표이다. 역은 $1$번부터 $n$번까지 번호가 매겨져 있다.
• 그다음 줄에는 방문하는 역들의 번호 $m$개가 방문 순서대로 주어진다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. 여기서 $x$는 데이터 집합의 번호이며 $1$부터 시작한다. 그다음 줄에 여정을 포함하는 가장 작은 직사각형 안에 들어가는 역의 총 개수를 출력한다. 연속한 두 데이터 집합 사이에는 빈 줄을 하나 넣어 구분한다.