Сколько пользователей ровно на k-м рукопожатии

Соцсеть хочет показывать «друзей друзей». Дан граф дружбы из n пользователей и m пар, пользователь s и число k. Посчитайте, сколько пользователей находятся от s на расстоянии ровно k рукопожатий (кратчайший путь из k рёбер). При k = 0 это сам s.

Ввод: в первой строке n и m (1 ≤ n ≤ 2500, 0 ≤ m ≤ 2500), далее m строк a b, в последней строке s и k (0 ≤ k ≤ n). Возможны петли и повторы пар.

Вывод: количество пользователей.

Пример 1

Ввод:

6 6
1 2
1 3
2 4
3 4
4 5
6 6
1 2

Вывод:

1

Пример 2

Ввод:

3 1
1 2
3 0

Вывод:

1