33626번 - 나는 뱀파이어 서브태스크

문제

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

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

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

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

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

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

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

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

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

입력

첫 번째 줄에 SRC의 연구실 수 $N,ドル 뱀파이어로 즉시 만들 수 있는 학생의 수 $M,ドル 피클이 있는 연구실 $P$가 공백으로 구분되어 주어진다.

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

출력

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

제한

• 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$

서브태스크

힌트