"あたしヴァンパイア, まずはこっちおいで!" (나는 뱀파이어, 일단은 이리로 와!)

하츠네 피클은 정말 유명한 뱀파이어이다.

어느 날, 피클은 연구의 날을 맞아 SRC(Science Research City)에 있는 모두를 뱀파이어로 만들어 버리기로 결심했다!

SRC는 $N$개의 연구실과 두 연구실 사이를 잇는 $N-1$개의 복도로 이루어져 있고, 임의의 한 연구실에서 다른 한 연구실로 이동하는 최단 경로는 항상 존재하며 유일하다. 다시 말해, SRC는 트리 구조로 이루어져 있다. 각 연구실은 $1$ 이상 $N$ 이하의 서로 다른 번호가 붙여져 있다. 피클은 $P$번 연구실에 있고, $P$번 연구실을 제외한 각 연구실마다 1명의 학생이 연구를 하고 있다.

피클은 이 계획을 실현하기 위해 철저한 준비를 해 두었는데, 바로 $M$명의 학생을 즉시 뱀파이어로 만들어버릴 수 있는 힘을 모아 둔 것이다!

계획이 시작될 때, 피클은 $M$명의 학생을 골라 즉시 뱀파이어로 만든다. 계획 시작 시 시간은 1이다.

이후 $1$의 시간이 지날 때마다, 모든 뱀파이어는 현재 있는 연구실에서 $P$번 연구실으로 가는 최단 경로를 따라 복도 하나를 이동한다. 뱀파이어가 아닌 학생은 연구에 몰두하고 있기 때문에 때문에 이동하지 않는다. $P$번 연구실에 도달한 뱀파이어는 이후에 이동하지 않는다.

이때, 뱀파이어와 뱀파이어가 아닌 학생이 같은 연구실에 있게 되면, 그 즉시 뱀파이어가 학생을 물어 학생이 뱀파이어로 변한다.

최대한 빠르게 모든 학생을 뱀파이어로 만들고 연구를 진행하고 싶은 피클을 위해, $M$명의 학생을 적절히 선택했을 때 모든 학생이 뱀파이어가 되는 데 걸리는 최소 시간을 구해 주자.

Input

첫 번째 줄에 SRC의 연구실 수 $N$, 뱀파이어로 즉시 만들 수 있는 학생의 수 $M$, 피클이 있는 연구실 $P$가 순서대로 주어진다.

두 번째 줄부터 $N-1$개의 줄에 $a_i, b_i$ 가 공백으로 구분되어 주어진다. 이는 $i$번째 복도가 $a_i$번 연구실과 $b_i$번 연구실을 연결한다는 의미이다.

Constraints

$2 \leq N \leq 100,000$

$1 \leq M \leq N-1$

$1 \leq P \leq N$

$1 \leq a_i , b_i \leq N, a_i \neq b_i$

Output

모든 학생이 뱀파이어가 되는 것이 불가능하면 -1을, 가능하면 걸리는 최소 시간을 출력한다.

Scoring

1. 모든 $i$ $(1 \leq i < n)$에 대해 $i$번 연구실과 $i+1$번 연구실을 잇는 복도가 존재하며, $P = 1$ (18점)

2. 모든 $i$ $(1 \leq i < n)$에 대해 $i$번 연구실과 $i+1$번 연구실을 잇는 복도가 존재한다. (12점)

3. $N \le 5000$ (30점)

4. 추가 제약 조건 없음. (40점)

Examples

Input 1

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

Output 1

2

Input 2

5 1 2
2 1
2 3
1 4
2 5

Output 2

-1

Input 3

9 4 1
1 2
1 3
2 4
2 5
4 6
3 7
7 8
8 9

Output 3

2

Note

https://www.youtube.com/watch?v=e1xCOsgWG0M