树上公约数
题号：NC260744
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个 n 个点的树，每条边具有一个边权。每条简单路径的长度为路径上点的数量，请问长度为 k 的简单路径的边权的最大公约数的最大值。

如果路径上没有重复的顶点，称这样的路径为简单路径。简单路径的边权的最大公约数是指该简单路径上所有边权的最大公约数。 

输入描述:

第一行两个正整数 n 和 k，表示树的大小和简单路径的长度。

接下来的 n - 1 行，其中第i行两个正整数 p_i 和 w_i，表示点 p_i 和点 i +1 之间存在一条边权为w_i的边。

输出描述:

输出一个正整数，表示长度为 k 的简单路径的边权的最大公约数的最大值。如果不存在长度为 k 的简单路径，那么输出 -1。
示例1

输入

复制 
20 3
1 2
2 7
3 6
2 1
4 1
4 8
2 1
1 7
1 1
10 8
4 8
10 10
4 8
1 6
9 6
2 3
7 1
3 7
8 9

输出

复制 
8

备注:

1 \leq k,p_i \leq n，p_i \leq i，1 \leq n,w_i \leq 200000