글 읽기 - 2215번 원형 네트워크 O(NP)보다 빨리 풀 수 없을까요?

원형을 직선으로 펼친 후 연장시켜서 O(NP)로 풀었는데....

문제가 원형이 아닌 경우에는 O(N)에 풀 수 있으니까 더 빨리 풀 수는 없을까 고민하게 되네요.

혹시 아시는 분은 답변 달아주시면 감사하겠습니다.