스쿽 바이러스

소셜 네트워크 Twitface가 바이러스 공격을 받고 있다. 바이러스는 사용자에서 사용자로 퍼지면서 통신량을 불려 네트워크를 마비시킨다. 평소에는 사용자가 직접 메시지를 보내야 하고 이 메시지를 스쿽이라고 부르는데, 감염된 스쿽은 사용자가 아무것도 하지 않아도 스스로 복제한다.

감염된 스쿽을 받은 사용자는 정확히 1분 뒤에 네트워크에서 자신과 연결된 모든 이웃에게 감염된 스쿽을 하나씩 보낸다. 한 사용자가 같은 시각에 스쿽을 여러 개 받으면, 1분 뒤에 이웃마다 받은 개수만큼 스쿽을 보낸다.

아래 네트워크를 보자. 사용자 0은 사용자 1, 3과 연결되어 있고, 사용자 2는 사용자 1, 3, 4와 연결되어 있다.

시각 $t = 0$에 사용자 0이 감염되면, $t = 1$에는 사용자 1과 3이 스쿽을 하나씩 받고, $t = 2$에는 사용자 0과 2가 두 개씩 받고, $t = 3$에는 사용자 1과 3이 네 개씩, 사용자 4가 두 개를 받는다. 시각 1, 2, 3에 오간 스쿽은 각각 2개, 4개, 10개다.

네트워크 구조와 처음 감염된 사용자가 주어진다. 시각 $t$에 오간 스쿽이 몇 개인지 구하여라. $t = 0$이면 사용자 $s$를 감염시킨 스쿽 하나를 센다.

첫 줄에 정수 네 개 $n$, $m$, $s$, $t$가 주어진다. $n$은 사용자 수($1 \le n \le 100$), $m$은 사용자를 잇는 연결의 개수($0 \le m \le n(n-1)/2$), $s$는 처음 감염된 사용자의 번호($0 \le s < n$), $t$는 지난 시간을 분으로 나타낸 값($0 \le t < 10$)이다.

다음 $m$개의 줄에는 정수 두 개 $x$와 $y$($0 \le x, y < n$)가 주어지며, 사용자 $x$와 $y$가 연결되어 있다는 뜻이다. 연결은 양방향이고, 같은 연결이 두 번 주어지지 않는다.

시각 $t$에 오간 스쿽의 개수를 출력한다.