$1$번부터 $N$번까지 $N$명의 아이들이 있다. 각 아이는 자기자신이 아닌 “베프"가 한 명씩 있다. 아이들 중 몇 명을 골라 원을 이루도록 앉혔을 때 원에 앉은 모든 아이의 바로 옆에 그 아이의 베프가 있도록 하고 싶다. 원에 앉을 수 있는 아이들의 수의 최댓값을 구하시오.

  • 공통 조건
    • 테스트 케이스의 개수 $T \le 100$
  • Small
    • $3 \le N \le 10$
  • Large
    • $3 \le N \le 1000$

Small 풀이

$_N P_1 + _N P_2 + \cdots + _N P_N$의 순열을 모두 만들어 보고 조건을 만족하는 순열의 최대 길이를 출력하면 된다.

Large 풀이

어떤 아이 $A$를 원에 넣는다고 생각해보자. 그러면 $A$의 베프인 $B$를 $A$의 옆에 앉혀야 하고, $B$의 베프인 $C$를 $B$의 옆에 앉혀야 하고, …를 반복하게 된다. 따라서 베프 관계를 functional graph로 생각할 수 있다.

한 functional graph의 임의의 노드에서 시작하여 유일한 엣지를 따라가다 보면 결국 어떤 사이클에 닿게 된다. 베프는 자기자신이 아니므로, 이 사이클의 길이는 항상 2 이상이다.

사이클의 길이가 3 이상이라면, 사이클 밖에서 시작한 경우에는 마지막으로 앉힌 아이의 베프를 바로 옆에 앉힐 방법이 없다. 사이클 안에서 시작한 경우 사이클이 완성될 때 가능한 하나의 원이 만들어지고, 모든 이웃한 아이들 사이에 엣지가 존재하므로 다른 아이를 더 추가할 수 없다.

사이클의 길이가 2인 경우가 중요하다. 사이클에 속한 두 아이를 $A$, $B$라고 하자. $a_1$의 베프가 $a_2$, $a_2$의 베프가 $a_3$, …, $a_i$의 베프가 $A$이고, $b_1$의 베프가 $b_2$, …, $b_j$의 베프가 $B$이면, $a_1, a_2, \cdots, a_i, A, B, b_j, \cdots, b_2, b_1$ 순서대로 배열하면 모두 자신의 베프와 이웃하게 앉게 된다. 또한, $a_1$과 $b_1$ 사이를 끊고 또 다른 아이들을 삽입할 수 있으므로, 이러한 체인이 여러 개 있다면 이들을 모두 하나의 원으로 합칠 수 있다.

$A$와 $B$를 포함한 체인의 길이는 $A$로 진입하는 최장 경로와 $B$로 진입하는 최장 경로를 합쳐서 구할 수 있다. 최장 경로를 구하는 방법은 여러 가지가 있을 수 있다. 본인은 간선을 모두 뒤집은 다음 $A$에서 시작해서 BFS를 하는 방법을 사용하였다. 사이클에 속한 노드들을 모두 판별한 후 트리 DP와 비슷한 방법도 가능할 것으로 보인다.

답은 max(가장 긴 사이클의 길이, 모든 2-사이클로부터 만들 수 있는 가장 긴 체인의 길이의 총합)이 된다.