点的分治（3）

题目描述:

给定一棵有n个点的树，每个点都权值vi，求是否存在一条路径使得路径上所有点的权值的乘积mod (10^6 +3)为k，输出路径首尾标号，若有多解输出字典序最小的解。

输入格式:

第一行两个数n,k。

第二行n个数表示vi。

接下来n-1行每行两个数x和y表示树上边。

输出格式:

输出两个数a,b（a<b)，若无解输出“No solution"。

样例输入:

样例1：
5 60
2 5 2 3 3
1 2
1 3
2 4
2 5

样例2：
5 2
2 5 2 3 3
1 2
1 3
2 4
2 5

样例输出:

样例1：
3 4

样例2：
No solution

提示:

1<=n<=10^5

0<= k <10^6+3

1<= vi <10^6+3

注意栈溢出的情况。

时间限制: 1000ms
空间限制: 256MB

---