섬 | cho.sh

IOI 나라는 특이하게도 정$N$각형 모양의 섬에 세워졌다. $N$개의 각 꼭짓점에 해당하는 위치마다 지역이 있으며, 이 지역들은 반시계 순서로 $0, 1, \dots , N - 1$의 번호가 붙어 있다. IOI 나라의 도로망은 다음과 같은 두 종류의 도로로 이루어진다:

해변 도로: 해변 도로는 정$N$각형의 인접한 꼭짓점에 해당하는 지역 사이를 연결하는 $N$개의 도로이다. 다시 말해, 모든 정수 $0 ≤ i ≤ N - 2$에 대해 $i$번 지역과 $i + 1$번 지역을 잇는 도로가 존재하며, $N - 1$번 지역과 $0$번 지역을 잇는 도로가 존재한다.
육지 도로: 해변 도로로 직접 연결되어 있지 않은 두 지역을 선분 형태로 연결하는 육지 도로들이 총 $N - 3$개 존재한다. 이 때, 각 육지 도로들은 끝점을 제외하고는 서로 만나지 않는다. 즉, 정$N$각형에서 교차하지 않는 서로 다른 대각선 $N - 3$개에 해당한다.

한편, $K$개의 지역을 잇는 어떤 도로망에 대해, 도로의 집합 $T$가 다음 조건을 만족할 때 $T$를 트리라고 한다.

$|T| = K - 1$
$T$에 포함된 도로만 이용해서 모든 지역 사이를 이동할 수 있다.

트리는 모든 지역을 연결하므로 운송에서 매우 중요한 역할을 차지한다. 하지만, 트리의 도로를 사용할 수 없을 때 이용할 수 있는 또 다른 트리가 있다면 안정성에 크게 도움이 될 것이다. 이에 도로망에 두 트리 $T_1$와 $T_2$가 존재하여 $T_1 \cap T_2 = ∅$를 만족할 때, 즉 어떠한 도로도 겹치지 않는 두 트리가 존재할 때, 그 도로망을 좋은 도로망이라고 정의한다.

IOI 나라에서는 다음과 같이 새로운 지역과 도로를 건설하는 방안을 통해 좋은 도로망을 구축하고자 한다.

지역 건설: 지역 $a$, $b$, $c$에 대해 $a$와 $b$ 사이, $b$와 $c$ 사이, $c$와 $a$ 사이를 직접 잇는 도로가 모두 존재할때, 세 지역이 이루는 삼각형의 내심에 새로운 지역 $d$를 만들고, $a$와 $d$ 사이, $b$와 $d$ 사이, $c$와 $d$ 사이를 도로로 연결한다. 새로운 지역 $d$의 번호는 $N$부터 순서대로 붙여진다. 동일한 세 지역에 대해서 지역 건설을 두 번 이상 할 수 없다. 다시 말해, 지역 건설에서 사용한 집합 $\{a, b, c\}$ 는 매 건설마다 서로 달라야 한다.

IOI 나라에서는 지역 건설을 여러 번 할 수 있지만, 가능한 적은 횟수의 지역 건설을 통해 겹치지 않는 두 트리가 존재하는 좋은 도로망으로 바꾸고자 한다. 좋은 도로망이 되기 위해서는 기존의 $N$개 지역뿐만 아니라 새로 건설된 지역도 연결하는 겹치지 않는 두 트리가 존재해야 함에 주의하라. 여러분은 IOI 나라를 도와 도로망 문제를 해결해야 한다. 지역 건설의 횟수를 최소화하지 않아도 부분 점수를 받을 수 있음에 유의하라.

섬

문제

제한