Description

Lyp是某旅行社一业务员，挑剔的客户老是爱问一些烦人的问题，如：从北京到上海最近的路线有多远？从南京到上海的有多少条路可以走？不过lyp干这行已经有那么一段时间了，这些问题基本也都没啥问题。现在客户有提出了这么一个问题：从地点S到地点T，在路线长度不超过最短路径k单位长的情况下，有多少条路径可供选择？

Input

输入数据包含多组； 对于每组数据，首先输入一个n,m(n3->2->3

Source: lyp