
ZOJ Problem Set  3172
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 7day 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. Note 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. Input
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. Output 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". Sample Input 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 Sample Output 8 Impossible Author: CHEN, Yue Source: ZOJ 7th Anniversary Contest 