34520번 - 트리 오델로 스페셜 저지

정점의 개수가 $N$개인 트리가 주어진다. 트리는 $1$번 정점을 루트로 하며, 간선의 개수는 $N−1$개이다.

트리의 각 간선에는 양의 가중치가 있으며, 두 정점 $u$, $v$ 사이의 거리는 $u$에서 $v$로 가는 단순 경로 위의 모든 간선 가중치 합으로 정의한다.

트리의 각 정점은 흰색이나 검은색 중 하나의 색을 가지며, 처음에는 트리의 모든 정점이 흰색이다. 이 트리에 대해 다음과 같은 연산을 사용할 수 있다.

• $0 \le k \le 10^9$인 정수 $k$를 하나 선택한다.
• 트리의 루트로부터 거리가 $k$ 이하인 모든 정점의 색을 흑백 반전한다. 즉, 정점이 흰색이라면 검은색으로, 검은색이라면 흰색으로 바꾼다.

이 연산을 최대 $N$번 사용하여, 트리에서 검은색인 정점의 개수를 정확히 $M$개로 만들 수 있는지 구해보자. 연산 횟수는 최소일 필요가 없지만, 반드시 $N$번 이하이어야 한다.

첫 번째 줄에 정수 $N$, $M$이 공백으로 구분되어 주어진다.

다음 $N-1$개의 줄에는 간선의 정보가 주어진다. 그중 $i$번째 줄에는 정수 $u_i,v_i, x_i$가 공백으로 구분되어 주어진다. 이는 $u_i$번 정점과 $v_i$번 정점을 잇는 간선의 가중치가 $x_i$임을 의미한다. $(1 \le i \le N - 1)$

만약 검은색인 정점의 개수가 정확히 $M$개가 될 수 있다면

• 첫 번째 줄에 연산의 횟수 $C$를 출력한다.
• 두 번째 줄에 각 연산에 사용될 음이 아닌 정수 $k_1, k_2, \cdots, k_C$를 공백으로 구분하여 출력한다. 이는 $j$번째 연산에서 선택한 정수가 $k_j$임을 의미한다. $(1 \le j \le C)$

만약 검은색인 정점의 개수가 정확히 $M$개가 될 수 없다면 첫 번째 줄에 -1을 출력한다.

• $1 \le M \le N \le 5\,000$
• $1 \le u_i, v_i \le N$
• $1 \le x_i \le 5\,000$
• $u \ne v$
• $1 \le C \le N$
• $0 \le k_j \le 10^9$