감찰

바이트란드 철도(BR)의 노선망은 양방향 선로로 이루어져 있다. 각 선로는 두 역을 직접 잇고, 어떤 두 역 사이에도 선로는 많아야 하나뿐이며, 임의의 두 역 사이에는 같은 역을 두 번 지나지 않는 경로가 정확히 하나 존재한다. 즉, 노선망은 $n$개의 역으로 이루어진 트리이다.

바이트아사르는 BR의 잠복 감찰관이다. 그는 역 하나를 골라 거점 $S$로 삼고, 나머지 모든 역을 감찰해야 한다. 이동 방식은 다음과 같다.

• 역 $S$에서 출발한다.
• 아직 감찰하지 않은 역 하나를 골라 최단 경로로 이동해 감찰한 뒤, 다시 $S$로 돌아온다.
• 부정한 직원들이 서로 그의 이동을 알리므로, 바이트아사르는 직전 이동과 다른 선로로 $S$를 떠나야 한다. 즉, 연속한 두 번의 이동은 $S$에서 같은 선로로 시작할 수 없다.
• $S$를 제외한 모든 역은 정확히 한 번씩 감찰한다.
• 마지막 역을 감찰한 뒤에는 $S$로 돌아오지 않는다.

선로 하나를 지나는 데 걸리는 시간은 모두 같으며, 한 시간이다.

바이트아사르는 모든 역을 거점 $S$의 후보로 고려한다. 각 $S$에 대해 올바른 감찰 순회의 최소 총 이동 시간을 구하라. 그러한 순회가 존재하지 않는 $S$라면 그 사실을 알려라.

첫 줄에 역의 수 $n$ ($1 \le n \le 1{,}000{,}000$)이 주어진다. 역은 $1$번부터 $n$번까지 번호가 매겨져 있다. 이어지는 $n-1$개의 줄에는 각각 두 정수 $a$, $b$ ($1 \le a, b \le n$, $a \ne b$)가 공백 하나로 구분되어 주어지며, 이는 역 $a$와 역 $b$를 직접 잇는 선로를 뜻한다. 모든 선로는 정확히 한 번씩 나열된다.

$n$개의 줄을 출력한다. $i$번째 줄에는 거점이 $S = i$일 때 모든 역을 감찰하는 데 필요한 최소 이동 시간(시간 단위)을 정수 하나로 출력한다. $S = i$에 대해 올바른 순회가 존재하지 않으면 $-1$을 출력한다.

그림은 예제의 노선망을 나타낸다. 모든 역을 감찰할 수 있는 경우는 $S = 2$뿐이며, 최적의 감찰 순서 중 하나는 $7, 4, 8, 6, 1, 5, 3, 9$로 총 $23$시간이 걸린다.