접히는 구조물

프랜시스는 생일 선물로 인기 있는 조립 장난감을 받았다. 이 장난감은 여러 개의 금속 구슬과, 길이가 모두 같은 단단한 막대들로 이루어져 있다. 각 막대의 양 끝에는 자석이 달려 있어 구슬 두 개를 이어 붙일 수 있으며, 막대는 구슬을 중심으로 어느 방향으로든 자유롭게 회전한다(구면 관절처럼 움직인다). 그래서 다양한 형태의 구조물을 만들 수 있다.

프랜시스는 여러 구조물을 만들었고, 이제 방 한쪽 구석에 걸어 보관하려고 한다. 그런데 어떤 구조물은 구슬 하나를 잡고 들어 올리면 중력과 자유롭게 회전하는 관절 때문에 모든 막대가 하나의 얇은 수직선으로 접혀 버린다(그림 참고). 프랜시스는 구조물의 구슬 하나를 천장에 고정해 걸며, 공간을 아끼기 위해 각 구조물을 접힌 선이 가장 짧아지는 구슬로 걸고 싶어 한다. 어떤 구슬로 걸어도 하나의 얇은 선으로 접히지 않는 구조물은 자리를 너무 많이 차지하므로 버린다.

그림: 프랜시스가 만든 구조물 중 하나(왼쪽), 같은 구조물이 길이 2인 직선 형태로 접힌 모습(가운데), 어떤 구슬로 걸어도 하나의 선으로 접히지 않는 구조물(오른쪽). 가운데 그림에서 구슬 사이에 그려진 가로 간격은 이해를 돕기 위한 것일 뿐이며, 수학적으로 이 구조물은 무한히 가는 하나의 수직선이다.

금속 구슬은 무한히 작은 점으로, 막대는 길이가 $1$인 선분으로 생각하자. 주어진 구조물을 구슬 하나로 걸었을 때 접힌 구조물의 가능한 가장 짧은 길이를 구하거나, 무한히 가는 직선 하나로 접히도록 걸 수 있는 구슬이 하나도 없음을 알려라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 완전히 연결된 구조물 하나를 나타낸다(떨어져 나온 부분은 없다).

각 테스트 케이스의 첫 줄에는 공백으로 구분된 두 정수 $n$과 $m$이 주어진다. $n$은 구슬의 수($1 \le n \le 100$), $m$은 막대의 수($0 \le m \le 1000$)이다. 구슬은 $1$부터 $n$까지 서로 다른 번호가 붙어 있다. 이어지는 $m$개의 줄에는 각각 두 정수 $a_i$와 $b_i$($1 \le a_i, b_i \le n$)가 주어지며, 이는 구슬 $a_i$와 구슬 $b_i$가 막대로 연결되어 있음을 뜻한다. 한 막대의 양 끝이 같은 구슬에 붙는 경우는 없고, 같은 구슬 쌍을 잇는 막대가 둘 이상인 경우도 없다.

연속한 테스트 케이스는 빈 줄로 구분된다. "0 0"만 있는 줄은 입력의 끝을 뜻하며, 이 경우는 처리하지 않는다.

각 테스트 케이스마다 접힌 구조물의 가능한 가장 짧은 길이를 한 줄에 출력한다. 어떤 구슬 하나로도 걸어서 직선으로 접을 수 없다면 대신 "impossible"을 출력한다.