树链是指树里的一条路径。

美团外卖的形象代言人袋鼠先生最近在研究一个特殊的最长树链问题。

现在树中的每个点都有一个正整数值，他想在树中找出最长的树链，使得这条树链上所有对应点的值的最大公约数大于 $1$。

请求出这条树链的长度。

第 1 行：整数 $n\ (1 ≤ n ≤ 100000)$，表示点的个数。

第 2~n 行：每行两个整数 $x,y$ 表示 $x$ 和 $y$ 之间有边，数据保证给出的是一棵树。

第 n+1 行：$n$ 个整数，依次表示点 $1\sim n$ 对应的权值（$1 ≤$ 权值 $≤ 1,000,000,000$）。