고양이와 쥐

정점이 $N$개이고 각 정점에 $1$번부터 $N$번까지 번호가 붙은 무향 트리에서 고양이와 쥐가 게임을 한다. 고양이는 $1$번 정점에서, 쥐는 $M$번 정점에서 시작한다. 트리의 각 간선에는 치즈가 놓여 있고, 그 양은 $1$부터 $N-1$까지 서로 다른 값이다. 둘은 번갈아 움직이며 쥐가 먼저 움직인다.

쥐는 자기 차례에 현재 정점에 연결된 간선 중 치즈가 가장 많은 간선을 따라 이웃 정점으로 간다. 그 이웃 정점에 고양이가 있으면 쥐는 치즈가 두 번째로 많은 간선을 따라 이웃 정점으로 간다. 갈 수 있는 두 번째 정점이 없으면 게임이 끝나고 고양이가 이긴다. 고양이는 자기 차례에 이웃 정점 하나로 이동하거나 제자리에 머무른다.

당신은 고양이를 조종하며 최대한 빨리 이기려고 한다. 고양이가 이길 때까지 쥐가 움직이는 횟수의 최솟값을 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 $N$과 $M$이 주어진다. 다음 $N-1$개의 줄에는 각각 두 정수 $u$와 $v$가 주어지고, 이는 정점 $u$와 정점 $v$를 잇는 간선을 뜻한다. 이 간선 중 $k$번째 간선($1 \le k \le N-1$)에 놓인 치즈의 양은 $k$이다.

제한

• $1 \le T \le 100$
• $2 \le N \le 2000$
• $1 \le M \le N$
• $1 \le u, v \le N$
• 각 테스트 케이스의 그래프는 트리이다.
• 모든 테스트 케이스의 $N$을 더한 값은 $5000$ 이하이다.
• 쥐는 간선의 치즈를 먹지 않는다. 따라서 각 간선의 치즈 양은 게임이 끝날 때까지 그대로다.
• 고양이는 쥐가 있는 정점으로 이동할 수 있다. 이때 쥐는 아무 피해도 입지 않고 게임은 평소대로 이어진다.

각 테스트 케이스마다 입력으로 주어진 순서대로, 고양이가 최적으로 움직일 때 고양이가 이길 때까지 쥐가 움직이는 횟수의 최솟값을 한 줄에 출력한다. 고양이가 이길 수 없으면 $-1$을 출력한다.