Vasya plays a popular game the Gnomes of Might and Magic. In this game Vasya manages the kingdom of gnomes, consisting of several castles, connected by bidirectional roads. The kingdom road network has a special form. The kingdom has m main castles a 1 , a 2 , ..., a m , which form the Good Path. This path consists of roads between the castles a i , a i + 1 (1 ≤ i < m ) as well as the road between a m and a 1 . There are no other roads between the castles of the Good Path. In addition, for each pair of neighboring Good Path castles u and v there is exactly one Evil Shortcut — a path that goes along the roads leading from the first castle ( u ) to the second one ( v ) and not having any common vertexes with the Good Path except for the vertexes u and v . It is known that there are no other roads and castles in the kingdom there, that is, every road and every castle lies either on the Good Path or the Evil Shortcut (castles can lie in both of them). In addition, no two Evil Shortcuts have any common castles, different than the castles of the Good Path. At the beginning of each week in the kingdom appears one very bad gnome who stands on one of the roads of the kingdom, and begins to rob the corovans going through this road. One road may accumulate multiple very bad gnomes. Vasya cares about his corovans, so sometimes he sends the Mission of Death from one castle to another. Let's suggest that the Mission of Death should get from castle s to castle t . Then it will move from castle s to castle t , destroying all very bad gnomes, which are on the roads of the Mission's path. Vasya is so tough that his Mission of Death can destroy any number of gnomes on its way. However, Vasya is very kind, so he always chooses such path between castles s and t , following which he will destroy the smallest number of gnomes. If there are multiple such paths, then Vasya chooses the path that contains the smallest number of roads among them. If there are multiple such paths stil