建中國有 N 座城市，其中有一些道路可以作為聯絡兩座城市之用。

對於每一個城市，為了方便起見，我們將他們依序編號成 1 到 N 的正整數；

而對於每一條聯絡道路，都是「雙向」的且恰好可以聯絡兩座城市 A_i 和 B_i，

意即可以利用該條道路從城市 A_i 到達城市 B_i，也可以從城市 B_i 經由這條道路到達城市 A_i。

由於在這個國家的城市之間充斥著許多聯絡道路，因此喜歡思考的曉涵就產生了一個疑問：

「如果我要從城市 S 前往城市 T，並且規定恰好要走過 K 條聯絡道路的話，有幾種走法呢？」(同一條連絡道路走過 n 次視為走過 n 條道路)

為了簡化題目，我們可以忽略城市內的交通網路，你可以將每個城市當作一個中繼站，

一旦進去馬上出來且城市內複雜的子道路將不應該被計算在經過的道路數中(其實你也不會知道 :P )。

此外，在經過 K 條路後恰好到達終點城市 T 之前經過城市 T 是被允許的，這種可能也應該被計算進去。

最後，一條邊可以重複走很多次不會毀損或壞掉。