题目描述

GZR 开发了一个社交平台，在这个社交平台上每个用户都可以发布图片、查看好友发布的图片或者转发好友的图片。且这个平台的用户都很奇怪，每个人看到好友的图片后都会立马转发。GZR 为了避免转发传播的太远，规定一张图片最多转发 $k$ 轮后就不能转发了。

如果 A 与 B 是好友，B 与 C 是好友，但 A 与 C 不是好友。那么A 发布了一张图片后 B 能看到，C 看不到。当 B 转发了 A 发布的图片后，C 就可以看到了，并且 C 也能转发这张图片给自己的好友查看和进一步转发。如果 C 转发了 “B 转发的图片”，那么我们称 C 的转发是第 $2$ 轮，B 的转发是第 $1$ 轮转发。

现在平台上有 $n$ 位用户，编号从 $1\sim n$。有 $m$ 对好友，好友关系是相互的。

编号为 $x$ 的用户发布了一张动物照片，编号为 $y$ 的用户发布了一张植物的图片，其他用户都没有发布任何图片。请问在 GZR 设置的最多 $k$ 轮转发限制下，多少用户既能看到动物图片，也能看到植物图片。

输入格式

第一行 $5$ 个整数 $n,m,x,y,k$。

接下来 $m$ 行每行包括两个整数 $u,v$，表示 $u,v$ 互相为好友。

输出格式

一行一个整数，表示在 GZR 设置的最多 $k$ 轮转发限制下，多少用户既能看到动物图片，也能看到植物图片。

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

1

样例解释

1,5 发布了图片，最多只能转发一轮。2,4 分别收到了图片并进行了转发，3 号用户接收到了 2,4 的转发。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,k\le 100$，$1\le m \le 1000$，$1\le x,y,u,v\le n$。