Boz günlər

Alisa buludlu bir ölkədə buludlu bir gündə səyahət edir, bu da onun yolu görməsini çətinləşdirir. Onun avtomobilində $k$ vahid yanacaq qalıb və hər yanacaq vahidi ona $1$ vahid məsafə qət etməyə imkan verir.

Ölkə bir neçə qarşılıqlı əlaqəli şəhərdən ibarətdir və Alisanın hazırda olduğu yeri bildiyiniz halda, bütün yanacağını sərf edərsə, onun ziyarət edə biləcəyi ümumi mümkün şəhərlərin sayını müəyyənləşdirməlisiniz.

Giriş verilənləri

Birinci sətir dörd tam ədəd ehtiva edir:

• $n$: Buludlu ölkədəki şəhərlərin sayı.

• $m$: Buludlu ölkədəki şəhərləri birləşdirən yolların sayı.

• $k$: Alisanın avtomobilindəki yanacaq vahidlərinin sayı.

• $c$: Alisanın cari şəhəri.

Növbəti $m$ sətir şəhərlər arasında yol əlaqəsini tam ədədlər cütü $u,v$ kimi təsvir edir, bu da şəhərlər $u$ və $v$ arasında iki tərəfli yol olduğunu göstərir.

Çıxış verilənləri

Bir tam ədəd çıxarın — Alisanın $k$ vahid yanacaq sərf edərək çata biləcəyi ümumi mümkün şəhərlərin sayı.

Nümunələr