1번에서 2번으로 가는 서로 다른 경로를 최대한 많이 찾으려고 하는데 문제 출력 단락에서 써져 있는 내용은

"첫째 줄에 왔다 갔다 할 수 있는 최대 횟수를 출력한다."

라고 하네요... 아마 2번 도시에서 1번 도시로는 어떻게든 돌아올 것이고, 이러한 행동을 여러번 할 것임이라고 추측할 수 있겠는데 문제 설명과 같이 해주면 좋을 것 같습니다.