#434 Spliting a tree

Loading problem...

Preparing the statement, recent submissions, and submit form.

#434 Spliting a tree | DOJ

Authors: woohyunjng

Statement

$N$ 개의 정점으로 이루어진 트리 $T$ 가 주어진다. 정점에는 $1,2,\cdots,N$ 의 번호가 붙어 있다.

정점 $v$ 와 음이 아닌 정수 $k$ 를 고른다. $v$ 와의 거리가 $k$ 이하인 모든 정점과 그 정점에 연결된 모든 간선을 트리에서 제거한다. 여기서 두 정점 사이의 거리는 두 정점을 잇는 단순 경로에 포함된 간선의 개수이다.

각 정점 $v$ 에 대하여, 제거한 뒤 남은 그래프의 연결 컴포넌트가 $2$ 개 이상이 되게 하는 최소의 $k$ 를 구하여라. 그러한 $k$ 가 없다면 $-1$ 을 구한다.

빈 그래프의 연결 컴포넌트 개수는 $0$ 이다.

입력은 다음과 같은 형식으로 주어진다.

$N$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_{N-1}\ v_{N-1}$

각 $i$ ( $1 \leq i \leq N-1$ )에 대하여 $u_i$ 번 정점과 $v_i$ 번 정점을 잇는 간선이 존재한다.

각 정점 $i$ 의 답을 $A_i$ 라고 하자. 첫째 줄에 $A_1,A_2,\cdots,A_N$ 을 공백으로 구분하여 출력한다.

Sample 1

Input

Output

-1

유일한 정점을 제거하면 빈 그래프가 되므로 연결 컴포넌트가 $2$ 개 이상이 될 수 없다.

Sample 2

Input

Output

-1 0 0 -1

$2$ 번 정점과 $3$ 번 정점은 자기 자신만 제거해도 트리가 두 컴포넌트로 나뉜다. 두 리프에서는 어떤 $k$ 를 골라도 두 컴포넌트 이상이 남지 않는다.

Sample 3

Input

Output

2 0 0 1 1