32026번 - Two trees, twelve forests 스페셜 저지

1번부터 N번까지 N개 정점과 M개 간선으로 이루어진 가중치 있는 무방향 단순 그래프 G에 대해 숲 점수를 다음과 같이 정의한다:

1. F₁, F₂, F₃, ⋯, F_M 각각을 1번부터 N번까지 N개 정점으로 이루어져 있으며 간선이 없는 그래프라 하자.
2. G의 간선들을 가중치 오름차순으로 e₁, e₂, ⋯, e_M이라 할 때, i = 1, 2, ⋯, M에 대해 순서대로 다음을 시행한다:
   • F_j에 e_i를 추가했을 때 사이클이 생기지 않는 최소의 양의 정수 j를 찾아 F_j에 e_i를 추가한다. 여기서 e_i를 추가한다는 것은 e_i의 양 끝 정점의 번호가 u_i, v_i일 때 F_j에 u_i번 정점과 v_i번 정점을 잇는 간선을 추가하는 것을 뜻한다.
3. F_i가 하나 이상의 간선을 가지는 가장 큰 i를 그래프 G의 숲 점수라 한다.

당신은 양의 정수 k에 대해 숲 점수가 정확히 k이고 정점이 2024개 이하인 그래프 G를 생성하라는 임무를 받았다.

이 문제가 너무 쉬웠던 당신에게는 다음과 같은 추가적인 조건을 만족하는 G를 찾는 것이 더 흥미롭게 느껴졌다.

• G의 정점의 개수를 N이라 하면, 간선의 개수는 (2N − 2)이다.
• G의 간선 중 (N − 1)개는 빨간색, 다른 (N − 1)개는 파란색으로 칠해서 빨간색 간선만 남겼을 때 트리가 되고, 파란색 간선만 남겨도 트리가 되도록 할 수 있다.

k가 주어질 때, 조건을 만족시키는 G를 구하여 출력해 보자.

첫 줄에 정수 k가 주어진다. (2 ≤ k ≤ 12)

첫 줄에 그래프 G의 정점의 개수 N을 출력한다. (2 ≤ N ≤ 2024)

둘째 줄부터 (2N − 2)개의 줄에 걸쳐 i번째 줄에 세 정수 a_i, b_i, c_i를 공백을 사이에 두고 출력한다. (1 ≤ a_i, b_i ≤ N; a_i ≠ b_i; 1 ≤ c_i ≤ 10⁹) 이는 a_i번 정점과 b_i번 정점을 잇는 가중치 c_i인 간선이 존재함을 나타낸다.

G는 다음 조건들을 충족해야 한다.

• 모든 간선의 가중치는 서로 다르다. 즉, c_i끼리는 서로 다르다.
• 출력한 첫 (N − 1)개의 간선은 트리를 이룬다. 마찬가지로, 그 뒤에 출력한 (N − 1)개 간선도 트리를 이룬다.
• 두 개 이상의 간선으로 직접 연결된 정점 쌍이 존재하지 않는다.
• G의 숲 점수는 k이다.

아래는 k = 3인 경우 올바른 답의 예시이다.

위 그래프는 아래 그림에서 확인할 수 있듯 겹치지 않는 두 개의 트리로 구성된다.

숲 점수를 계산해 보면 아래와 같이 3이 된다. 빨간색 간선은 F₁, 파란색 간선은 F₂, 초록색 간선은 F₃에 소속된 간선을 나타낸다.