섬

IOI 나라는 정$N$각형 모양의 섬에 세워졌다. $N$개의 각 꼭짓점에는 지역이 있다. 지역들은 반시계 방향 순서로 $0, 1, \dots, N-1$번이 붙어 있다.

IOI 나라의 도로망은 다음 두 종류의 도로로 이루어진다.

• 해변 도로: 정$N$각형에서 인접한 꼭짓점의 지역을 잇는 $N$개의 도로이다. 모든 정수 $0 \le i \le 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 = \emptyset$을 만족하면, 즉 어떤 도로도 두 트리에 함께 속하지 않으면 그 도로망을 좋은 도로망이라고 한다.

IOI 나라는 좋은 도로망을 만들기 위해 지역 건설을 원하는 만큼 할 수 있다. 지역 $a$, $b$, $c$에 대해 $a$와 $b$, $b$와 $c$, $c$와 $a$를 직접 잇는 도로가 모두 있으면, 삼각형 $abc$의 내심에 새 지역 $d$를 만들고 $d$를 $a$, $b$, $c$와 각각 도로로 잇는다. 새 지역은 $N$번부터 만들어진 순서대로 번호를 받는다. 같은 집합 $\{a, b, c\}$에 대해서는 지역 건설을 두 번 이상 할 수 없다.

지역 건설 횟수를 가능한 적게 하여 좋은 도로망으로 바꾸는 것이 목표다. 건설 후에는 원래의 $N$개 지역과 새로 건설된 지역을 모두 연결하는 서로 겹치지 않는 두 트리가 있어야 한다. 건설 횟수를 최소화하지 못해도 부분 점수를 받을 수 있다.

• $3 \le N \le 200\,000$
• 모든 $0 \le i \le N-4$에 대해:
  • $0 \le U[i], V[i] \le N-1$
  • $U[i] \ne V[i]$
  • 주어지는 $U$와 $V$는 지문에 나온 육지 도로 조건을 만족한다.