CS2: T-spawn'ni to'sish

Xarita \(V\) ta xona (tugun) va ular orasidagi \(E\) ta ikki tomonlama koridor (qirra) ko'rinishida berilgan. Terroristlar \(S-\)xonada (\(T-\)spawn) boshlanadi va \(T-\)xonaga (bombasite) yetib borishni xohlaydi.

Sizning jamoangiz istalgan xonada (\(S\) va \(T\) dan tashqari — o'z spawningizni yoki bombasitening o'zini "to'sib" bo'lmaydi) \(1\) ta o'yinchi qo'yib, o'sha xonani to'liq yopib qo'yishi mumkin: agar terroristlar shu xona orqali o'tishga uringanida, ular albatta ko'rinadi va to'xtatiladi — ya'ni to'silgan xona orqali o'tish umuman mumkin emas.

Koridorlarning o'zi (ikki xona orasidagi yo'l) to'sib bo'lmaydi — faqat xonalarni. Bitta xonaga nechta odam qo'ysangiz ham, u faqat bitta marta "to'silgan" hisoblanadi (qo'shimcha odam foyda bermaydi).

Sizga: terroristlar \(S\) dan \(T\) ga hech qanday yo'l bilan (to'silmagan xonalar orqaligina) yeta olmasligi uchun, minimal nechta xonani to'sish kerakligini toping.

Agar \(S\) va \(T\) orasida to'g'ridan-to'g'ri koridor mavjud bo'lsa (ya'ni ular bevosita qo'shni bo'lsa), ularni hech qanday xona sonini to'sib ajratib bo'lmaydi (chunki bu yo'lda to'siladigan xona umuman yo'q) — bunday holatda \(-1\) chiqaring.

Kiruvchi ma'lumotlar

Birinchi qatorda \(V, E, S, T\) (\(2 \le V \le 500\); \(1 \le E \le 2000\); \(1 \le S, T \le V\); \(S \neq T\)) — mos ravishda xonalar soni, koridorlar soni, \(T-\)spawn xonasi va bombasite xonasi.

Keyingi \(E\) ta qatorning har birida: \(u, v\) (\(1 \le u, v \le V\); \(u \neq v\), bir xil juftlik bir necha marta takrorlanishi mumkin) — \(u\) va \(v\) xonalari orasida koridor borligini bildiradi.

Chiquvchi ma'lumotlar

Terroristlarni \(S\) dan \(T\) ga yetib borishini butunlay to'sish uchun kerak bo'ladigan minimal xonalar sonini chiqaring. Agar \(S\) va \(T\) bevosita qo'shni bo'lsa \(-1\) chiqaring.

Misollar

1

4 4 1 4
1 2
1 3
2 4
3 4

2

2

5 6 1 5
1 2
1 3
2 4
3 4
2 3
4 5

1

3

2 1 1 2
1 2

-1