I need some thoughts on this algorism

no complete code needed but I need maybe brief algorism or explanation of what I need to do.

1.2 Problem You are a band manager in charge of a band who has decided to do a performance tour across different cities. They haven't decided the route yet and you want to help them plan it. The performance tour is going to take place in a region that has N cities, and there are M two-way streets between cities. The tour is going to last for several weeks: Every week, the band is going to perform at different cities from Monday to Saturday so that consecutive cities are connected by a street. The band will rest during Sunday. The tour is designed so that every Monday, the band will perform at the same city they performed the Saturday of the previous week. During the first week the tour will start at city numbered 1. The 6 cities they perform during each week should be all different, but they can come back to the same city during different weeks. Your goal is to design such a tour so that it starts from city 1 on the Monday of the first week and end at city N on the Saturday of the last week. You want the tour to last as few weeks as possible. You are asked to write a problem to decide if such a tour can be arranged. If it can be arranged, output the shortest time the tour takes (in number of weeks). Otherwise, output - 1 if such a tour is impossible. 1.3 Input Input should be read in from stdin. The first line will contain two space-separated integers N and M: the number of cities and the number of roads. Each of the following M lines will contain two integers u and v, denoting that there exists a road directly connecting city u and v. It will always be uv