Page not loading? Try clicking here.
Placeholder

#3510
Subtask

광고 뿌리기 1s 1024MB

Problems

규현이는 트리 모양의 도시에서 오토바이를 타고 정올학원 광고를 뿌리려고 한다. 규현이의 목표는 정올학원에서 출발하여 모든 노드에 광고를 뿌리고, 다시 정올학원으로 돌아오는 것이다. 규현이는 힘이 좋기 때문에 현재 노드에서 거리가 D 이하인 모든 노드에 광고를 뿌릴 수 있다.

날씨가 매우 덥기 때문에, 규현이는 최소한만 이동해서 목표를 달성하고 싶다! 규현이를 위해 규현이가 이동해야 하는 총 거리를 구해주자.


Input

첫번째 줄에는 노드의 개수 N( 1 \leq N \leq 100\ 000 )과 정올학원의 위치 S( 1 \leq S \leq N ), 규현이의 힘 D( 0 \leq D \leq N )가 주어진다.

두 번째 줄부터 N번째 줄까지, 트리의 간선 정보를 의미하는 두 자연수 x, y가 공백으로 구분되어 주어진다. 이는 x번 노드와 y번 노드가 연결되어 있음을 의미한다. (1 \leq x, y \leq N, x \neq y)

주어지는 연결관계는 트리를 구성하며, 모든 간선의 길이는 1이다.


Output

규현이가 목표를 완수하기 위해 이동해야 하는 최소 거리를 출력하여라.


Subtask

# Score Condition
#110

1 \le N \le 100, 0 \le D \le 5

#225

0 \le D \le 5

#365

추가 제약조건은 없다.


Example 

6 1 1
1 2
2 3
2 4
3 5
5 6
6

1 → 2 → 3 → 5 → 3 → 2 → 1 경로로 움직이면 된다. 규현이가 2번 노드에 있을 때 4번 노드에 광고를 뿌리고, 5번 노드에 있을 때 6번 노드에 광고를 뿌리면 된다.



Source

UCPC 2020 본선 A번

You must sign in to write code.