HŽ

면접 대비

시간 제한1초메모리 제한1024 MB

요약

승차권 구간에 닫힌 구간이 포함되는 승차권 수, 버스 표시가 없도록 다시 열어야 하는 구간의 최소 개수, 닫힌 구간이 없는 역의 최장 연속 길이를 구합니다.

난이도: 쉬움10점 중 3점
유형: 구간, 누적 합
정답자: 아직 제출이 없습니다

문제

하나의 철도 노선에 1부터 $N$ 까지 번호가 붙은 $N$ 개의 역이 있다. 보수 공사로 선로의 $K$ 개 구간이 폐쇄되었다. 폐쇄 구간에서는 양방향 모두 열차가 운행되지 않으며, 승객은 그 구간을 버스로 이동한다. 각 폐쇄 구간은 시작 역과 끝 역으로 주어진다.

다음 상황을 생각해 보자. 승객이 $X$ 역에 도착해 $Y$ 역까지 가는 표를 산다. $X$ 역에서 $Y$ 역까지 경로의 일부라도 버스로 이동하면, 그 사실을 표에 반드시 적어야 한다. 이러한 상황은 $M$ 개 있다.

다음 질문에 답하라.

$M$ 장의 표 중에서 경로의 일부 또는 전부가 버스 이동이라고 적힌 표는 몇 장인가?
$M$ 장의 표 어디에도 버스 경고가 적히지 않으려면, $K$ 개 구간 중 최소 몇 개를 개통해야 하는가?
열차로만 이동할 수 있는 가장 긴 철도 구간은 역의 개수로 몇 개인가?

입력

첫째 줄에 자연수 $N$ ( $1 \le N \le 1000$ )이 주어진다.

둘째 줄에 자연수 $K$ ( $1 \le K \le 1000$ )가 주어진다.

이어서 $K$ 개의 줄에 $i$ 번째 폐쇄 구간의 시작 역 $P_i$ 와 끝 역 $K_i$ 가 주어진다( $1 \le P_i \le N$ , $1 \le K_i \le N$ , $P_i \ne K_i$ ). 폐쇄 구간끼리는 겹치지 않는다.

다음 줄에 자연수 $M$ ( $1 \le M \le 1000$ )이 주어진다.

이어서 $M$ 개의 줄에 $i$ 번째 상황의 역 $X_i$ 와 $Y_i$ 가 주어진다( $1 \le X_i \le N$ , $1 \le Y_i \le N$ , $X_i \ne Y_i$ ).

출력

첫째 줄에 첫 번째 질문의 답을 출력한다.

둘째 줄에 두 번째 질문의 답을 출력한다.

셋째 줄에 세 번째 질문의 답을 출력한다.

힌트

첫 번째 예제에서 8번 역부터 11번 역까지 구간에 공사가 있어서, 첫 번째, 두 번째, 네 번째 승객의 표에 버스 이동이 적힌다. 이 구간을 개통하면 모든 승객이 열차만 타고 이동한다. 공사가 없는 가장 긴 구간은 11번 역에서 18번 역까지(또는 1번 역에서 8번 역까지)이며, 길이는 8개 역이다.

예제3

예제 1

입력

예상 출력

3
1
8

예제 2
입력
```
20
3
16 12
8 2
17 20
2
2 1
9 4
```
예상 출력
```
1
1
5
```
예제 3
입력
```
12
1
4 8
4
6 8
9 10
6 8
5 8
```
예상 출력
```
3
1
5
```