76 - ZOJ 7th Anniversary Contest - F
CYJJ is planning on her vacation. Since her boss has permitted her to stay at each city for a day with as many cities to visit as she like, she would try to extend her 7-day vacation as much as possible. With a map of highways connecting the cities in hands, she would like to find such two cities that there are the most number of cities on the path between them.
the map shows that all the cities are connected either directly or indirectly by highways. However, to return to where she was, CYJJ would have to pass at least one highway twice.
Each case starts with a line containing the number of cities N (1 <= N <= 1000), hence the cities are numbered from 0 to N - 1, and the number of highways M. Then M lines follow, each contains the two cities that a highway is directly adjacent to.
For each test case, if it is possible to extend CYJJ's vacation, output in a line the maximum number of days she can take to have the vacation. Or if it is impossible, print in a line "Impossible".
10 9 0 8 0 1 1 2 1 3 3 4 4 5 5 7 5 6 6 9 5 4 0 1 1 2 1 3 3 4
Author: CHEN, Yue
Source: ZOJ 7th Anniversary Contest