시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB64480.000%

문제

Na jednoj pruzi postoji N željezničkih postaja označenih brojevima od jedan do N. Zbog obnove, K dijelova pruge je zatvoreno, na njima se ne može prometovati niti u jednom smjeru te se na tim dijelovima putnici prevoze autobusima. Dijelovi pruge koji su zatvoreni zadani su svojim početnim i završnim postajama.

Zamislimo sada jednu situaciju. Putnik dođe na postaju X te kupi kartu za putovanje do postaje Y. Ako se na putu između postaja X i Y putnici u nekom trenutku prevoze autobusima, to treba obavezno pisati na kupljenoj karti. Zamislimo da proučavamo M takvih situacija.

Odgovori na sljedeća pitanja:

  1. Na koliko je, od M kupljenih karti, pisalo da se dio ili cijeli put putnici prevoze autobusima?
  2. Koliko najmanje od K dijelova treba otvoriti da na niti jednoj od M karti ne piše upozorenje?
  3. Koliki je najdulji dio pruge, izražen u broju postaja, na kojem se možemo voziti samo vlakom?

입력

U prvom je retku prirodan broj N (1 ≤ N ≤ 1000), broj iz teksta zadatka.

U drugom je retku prirodan broj K (1 ≤ K ≤ 1000), broj iz teksta zadatka.

U sljedećih K redaka nalaze se po dva prirodna broja Pi (1 ≤ Pi ≤ N) i Ki (1 ≤ Ki ≤ N, Pi ≠ Ki), oznake početne i završne postaje na i-tom zatvorenom dijelu pruge. Zadani zatvoreni dijelovi se ne sijeku.

U sljedećem je retku prirodan broj M (1 ≤ M ≤ 1000), broj iz teksta zadatka.

U sljedećih M redaka nalaze se po dva prirodna broja Xi (1 ≤ Xi ≤ N) i Yi (1 ≤ Yi ≤ N, Xi ≠ Yi), oznake postaja iz teksta zadatka za i-tu promatranu situaciju.

출력

U prvi redak ispiši cijeli broj, odgovor na prvo pitanje iz teksta zadatka.

U drugi redak ispiši cijeli broj, odgovor na drugo pitanje iz teksta zadatka.

U treći redak ispiši cijeli broj, odgovor na treće pitanje iz teksta zadatka.

예제 입력 1

20
2
18 20
8 11
5
14 10
8 11
6 8
8 18
14 17

예제 출력 1

3
1
8

예제 입력 2

20
3
16 12
8 2
17 20
2
2 1
9 4

예제 출력 2

1
1
5

예제 입력 3

12
1
4 8
4
6 8
9 10
6 8
5 8

예제 출력 3

3
1
5

힌트

Opis prvog probnog primjera: Zbog radova na dionici pruge od 8. do 11. postaje prvom, drugom i četvrtom putniku će na karti pisati da se prevoze autobusom. Ako bi otvorili navedenu dionicu, svi bi putnici putovali samo vlakom. Najdulja dio pruge na kojem nema radova, tj. putnici se ne prevoze autobusima je od 11. do 18. (može i od 1. do 8.) postaje u duljini od 8 postaja.