题目描述

小明是今年参加复试的外校考生，他要去民主楼小礼堂签到。由于对中南大学校本部很不熟悉，小明找到了这边读书的好朋友鲁大师，不巧，鲁大师在忙着自由探索项目的结题工作，不能给他带路，只好给他发了一份半成品的电子地图。地图上只列出了校本部内的 $N$ 个点，$M$ 条路，小明处于 $S$ 点，民主楼小礼堂是 $T$ 点。小明感谢鲁大师，当然只是在拿到地图的一瞬间，后面的情况让他知道这半成品到底有多坑。鲁大师制作的电子地图是带有语音提示功能的，但是在编号为奇数的点他要等 $1$ 分钟才能告诉他具体怎么走，而在编号为偶数的点要等 $2$ 分钟。现在告诉你地图的具体情况，小明想知道他能不能在 $A$ 分钟内赶到民主楼小礼堂。

输入格式

输入数据有多组，每组占 $M+1$ 行，第一行有 $5$ 个数字 $N,M,S,T,A$。