대한민국은 N개의 도시와 M개의 양방향 도로로 나타낼 수 있다.

대한민국의 대통령이 된 장태환은 지역 순회를 하고자 한다.

지역 순회를 하는 장태환은 어떤 도시에서 출발하여 도로를 따라 이동한 뒤 출발했던 도시로 도착한다.

지역 편애 논란이 생기면 안 되기 때문에, 어떤 도시도 두 번 방문할 수는 없다.(출발은 방문에서 제외하지만, 도착은 방문에 포함한다.)

또한, 지역 순회에서 할 행사들의 계획을 지키기 위해서는, 방문하는 도시의 수는 홀수가 되어야 한다.

이 조건을 따라 장태환이 전국 순회를 할 때, 장태환이 방문할 가능성이 있는 도시의 수를 구하여라.

지역 순회 timer 1s memory 128MB

지역 순회 1s 128MB