Huanhuan is always working on fansy programming questions. However, today he decided to give himself a break and travel to a beautiful country. Therefore, another problem arose. There are totall
Huanhuan is always working on fansy programming questions. However, today he decided to give himself a break and travel to a beautiful country. Therefore, another problem arose. There are totally n cities in the country. There are m two-way roads, each of them directly connects two different cities. As the country has a solid transportation system, there is always a path connects every two cities. Huanhuan arrives at city S and wants to carry as many items as possible to city T. Everyday he will go through exactly one road. For every road he pass, a fee is to pay. Due to the policy, the fee depends on number of items you carry and the number of days you enter the country. More exactly, the fee for each road is kd, where k is the number of the items Huanghuan is to carry and d is the number of days he enter the country. For example , Huanghuan arrives ar city 1 , and aim to city 3. The path he chooses is 1->2->3 carrying 2 items . Then the fee of road 1->2 will be 21 and the fee of road 2->3 will be 22. So the total expense is 21+22=6 Now, you are tasked to help him to decide the maximum number of items he can carry since he only have limited budget. However, Huanhuan is prepared to travel multiple times in the future. There will be totally Q query for you.
