The "Road Accident" band is planning an unprecedented tour around Treeland. The RA fans are looking forward to the event and making bets on how many concerts their favorite group will have.
Treeland consists ofncities, some pairs of cities are connected by bidirectional roads. Overall the country hasn-1roads. We know that it is possible to get to any city from any other one. The cities are numbered by integers from 1 ton. For every city we know its valueri— the number of people in it.
We know that the band will travel along some path, having concerts insomecities along the path. The band’s path will not pass one city twice, each time they move to the city that hasn’t been previously visited. Thus, the musicians will travel along some path (without visiting any city twice) and in some (not necessarily all) cities along the way they will have concerts.
The band plans to gather all the big stadiums and concert halls during the tour, so every time they will perform in a city which population islargerthan the population of the previously visitedwith concertcity. In other words, the sequence of population in the cities where the concerts will be held isstrictly increasing.
In a recent interview with the leader of the "road accident" band promised to the fans that the band willgive concertin the largest possible number of cities! Thus the band will travel along some chain of cities of Treeland and have concerts in some of these cities, so that the population number will increase, and the number of concerts will be the largest possible.
The fans of Treeland are frantically trying to figure out how many concerts the group will have in Treeland. Looks like they can’t manage without some help from a real programmer! Help the fans find the sought number of concerts.
，大多数人想要改造这个世界，但却罕有人想改造自己。
