#2517. 摩天大树

摩天大树

Description

有一棵摩天大树,在树的每个分支节点 上都有一个整数,可否在树上找到这样一个链,以便链上所有整数的乘 积(modmod 10610^6 +3+3)都等于kk

Format

Input

输入包含几个测试用例。每个测试用例的第1行都包含两个 整数N1N105N (1≤N ≤10^5 )k0k<106+3k (0≤k <10^6 +3)。接下来的一行包含NN 个 数字vi1vi<106+3vi (1≤v_i <10^6 +3),其中viv_i 表示节点ii 上的整数。然后是N1N -1 行,每行都包含两个整数xxyy ,表示节点xx 和节点yy 之间的无向边。

Output

对每个测试用例,都单行输出两个整数aaba<bb (a <b ), 表示满足条件的链的两个端点。若存在多个解决方案,则输出字典顺序 最小的解决方案。若不存在解决方案,则输出“No solution”。

Samples

5 60
2 5 2 3 3
1 2
1 3
2 4
2 5
5 2
2 5 2 3 3
1 2
1 3
2 4
2 5
3 4
No solution

来源

HDU4812