Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3172
Extend 7-day Vacation

Time Limit: 1 Second      Memory Limit: 32768 KB

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.
Consective cases are separated by an empty line.


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


Author: CHEN, Yue
Source: ZOJ 7th Anniversary Contest
Submit    Status