E. Найз бүсгүйтэйгээ уулзах

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Урпал том хотод амьдардаг. Тэр хайртай бүсгүйтэйгээ өнөө орой уулзахаар төлөвлөсөн.

Уг хот $1$-с $n$ хүртэл дугаарлагдсан $n$ уулзвартай. Уулзварууд нь $m$ ширхэг чиглэлтэй гудамжаар холбогдсон, бүх зам ижил урттай. Урпал $a$ уулзвар дээр амьдардаг ба болзоо $b$ уулзвар дээр байдаг ресторанд болохоор төлөвлөгдсөн. Тэр $b$ уулзварт очихын тулд нийтийн тээврийг ашиглахыг хүсч байна. Энд $k$ ширхэг автобусны компаниуд байдаг. Секунд бүрийн эхэнд $i$-р компанийн автобус $s_{i}$ уулзвар болон $t_{i}$ уулзваруудын хоорондох хамгийн богино замыг сонгон дайрч өнгөрдөг. $s_{i}$ болон $t_{i}$ хоёрын хооронд зам байхгүй байж болно. Энэ тохиолдолд ямар ч автобус $s_{i}$-с $t_{i}$-руу явахгүй. Хэрвээ автобус Урпалын зогсож буй уулзвараар дайрч өнгөрөх юм бол тэр автобусанд сууж чадна. Мөн тэр автобусны явах замын дагуух аль ч уулзвар дээр бууж чадна.

Одоо Урпал нийтийн тээврээр хязгаарлагдмал цагийг зарцуулан (зорчсон хугацаа нь зорчсон замуудын уртын нийлбэр байна) болзоондоо очиж чадах эсэхээ мэдэхийг хүсч байгаа ба хамгийн муу тохиолдолд тэр хэдэн автобус дамжихаа мэдэхийг хүсч байна.

Хором бүрт Урпал өөрийн байрлал болон болзоо болох газрыг л мэднэ. Тэр автобусанд суугаад уг автобусны компаний индексийг л мэднэ. Урпал хотын газрын зургийг мэдэх ба компани бүрийн хувьд $(s_{i}, t_{i})$ хосуудыг мэднэ.

Урпал автобуснуудын хурдыг мэдэхгүй.

Оролт

Оролтын эхний мөрөнд дөрвөн бүхэл тоон утга $n$, $m$, $a$, $b$ $(2 ≤ n ≤ 100; 0 ≤ m ≤ n*(n - 1); 1 ≤ a, b ≤ n; a ≠ b)$ байна.

Дараагийн $m$ мөр бүрт хоёр бүхэл тоон утга $u_{i}$ ба $v_{i}$ $(1 ≤ u_{i}, v_{i} ≤ n; u_{i} ≠ v_{i})$ агуулах ба $u_{i}$ уулзвараас $v_{i}$ уулзвар хүрэх чиглэлтэй замыг тодорхойлно. Оролтын бүх замууд ялгаатай байх болно.

Дараагийн мөрөнд бүхэл тоон утга $k$ $(0 ≤ k ≤ 100)$ байна. Үүний дараа $k$ мөр байх ба мөр бүр хоёр бүхэл тоон утга $s_{i}$ ба $t_{i}$ $(1 ≤ s_{i}, t_{i} ≤ n; s_{i} ≠ t_{i})$ агуулах ба энэ нь $s_{i}$-с эхлэж $t_{i}$-д дууссан автобусны чиглэл байна гэсэн үг. $s_{i}$ болон $t_{i}$ хоёрын хооронд зам байхгүй байж болох ба энэ тохиолдол бодлогын нөхцөлд тодорхойлогдсон байгаа.

Гаралт

Оролтын ганц мөрөнд Урпал хамгийн муу тохиолдлоор очих газраа очиход хамгийн багадаа хэдэн автобус дамжихыг илэрхийлсэн тоог хэвлэнэ. Хэрвээ хүрэх газраа хүрч чадахааргүй бол -1-г хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
7 8 1 7
1 2
1 3
2 4
3 4
4 6
4 5
6 7
5 7
3
2 7
1 4
5 7
Гаралт
2
Оролт
4 4 1 2
1 2
1 3
2 4
3 4
1
1 4
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...