eolymp
bolt
Try our new interface for solving problems
Məsələlər

Nəqliyyat sistemi

Nəqliyyat sistemi

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Bakı şəhərinin yol-nəqliyyat sistemi n qovşaq və bu qovşaqları bir-biri ilə birləşdirən m qoşa-istiqamətli yoldan ibarətdir. Hər bir yol iki müxtəlif qovşağı birləşdirir və eyni iki qovşağı birbaşa birləşdirən birdən çox yol ola bilməz. Eyni zamanda bu yollardan istifadə etməklə şəhərdə istənilən qovşaqdan istəniləninə getmək olar. İki qovşaq arasındakı məsafə bu qovşaqları birləşdirən bütün mümkün marşrutlardakı minimum yolların sayına bərabədir.

Nəqliyyat sistemini gücləndirmək üçün, şəhərin meri yol idarəsinin müdirindən yeni bir yol çəkməyi tələb etdi. Lakin, müdir təzə maşın alıb və hər gün evdən işə və işdən evə təzə maşını ilə sürməkdən həzz alaraq gedir. O istəmir ki, onun evinin yerləşdiyi qovşaq — s və iş yerinin yerləşdiyi qovşaq — t arasındakı məsafə azalsın. Bu işdə yol idarəsinin müdirinə kömək edin. O mütləq merin tələbini yerinə yetirməlidir.

Sizin tapşırığınız mövcud yol-nəqliyyat sistemində aralarında yol olmayan elə qovşaqlar cütünün sayını tapmaqdır ki, onlar arasında qoşa-istiqamətli yol çəkilsə st qovşaqları arasındakı məsafə azalmayacaq.

Giriş verilənləri

Birinci sətirdə dörd tam ədəd n~(1 \le n \le 10^3) — qovşaqların sayı, m~(1 \le m \le 10^5) — yolların sayı, s — evin yerləşdiyi qovşaq, t — iş yerinin yerləşdiyi qovşaq verilir (1 \le s, t \le n, s \ne t). Növbəti m sətrin i-cisində boşluqla ayrılmış iki tam ədəd u_iv_i~(1 \le u_i, v_i \le n, u_i \ne v_i) verilir. Bu o deməkdir ki, u_iv_i qovşaqları arasında qoşa-istiqamətli yol var.

Çıxış verilənləri

Çıxışa məsələnin şərtini ödəyən qovşaqlar cütünün sayını verin.

Nümunə

Giriş verilənləri #1
5 4 1 5
1 2
2 3
3 4
4 5

Çıxış verilənləri #1
0
Giriş verilənləri #2
5 4 3 5
1 2
2 3
3 4
4 5


Çıxış verilənləri #2
5
Mənbə Azərbaycan Respublika Olimpiadasının yarımfinalı 2018-2019