Squawk Virus

The social networking site Twitface is under attack by a virus. The virus spreads from user to user and floods the network with traffic. Users normally send messages to each other by hand, and such a message is called a squawk, but an infected squawk copies itself with no user action.

A user who receives an infected squawk sends one infected squawk to every neighbor in the network exactly one minute later. If a user receives several squawks at the same moment, one minute later it sends that many squawks to each of its neighbors.

Consider the network below. User 0 is linked to users 1 and 3, and user 2 is linked to users 1, 3 and 4.

If user 0 is infected at time $t = 0$, then at $t = 1$ users 1 and 3 receive one squawk each, at $t = 2$ users 0 and 2 receive two squawks each, and at $t = 3$ users 1 and 3 receive four squawks each while user 4 receives two. The number of squawks sent at times 1, 2 and 3 is 2, 4 and 10.

You are given the layout of the network and the first infected user. Find how many squawks are sent at time $t$. At $t = 0$, count the single squawk that infected user $s$.

The first line has four integers $n$, $m$, $s$, $t$: the number of users ($1 \le n \le 100$), the number of links between users ($0 \le m \le n(n-1)/2$), the index of the first infected user ($0 \le s < n$), and the elapsed time in minutes ($0 \le t < 10$).

Each of the next $m$ lines has two integers $x$ and $y$ ($0 \le x, y < n$), meaning that users $x$ and $y$ are linked. Links work in both directions, and no link is given twice.

Print the number of squawks sent at time $t$.