某天，喵喵被犬犬莫名其妙的传送到了犬犬国的首都root，犬犬国是一棵树，一共n个城市，有n-1条路连接，城市与城市之间都连通。

令人吃惊的是，喵喵不知道用什么方法，得知了犬犬国各个城市的狗粮种类数ti（即每个城市有ti种狗粮，不同城市狗粮不同），于是乎喵喵想一边游玩犬犬国，一边品尝各种口味的狗粮。(喵喵很好吃，吃腻了猫粮，想多尝尝狗粮)。而喵喵从一个城市s，走到相邻的一个城市t，当且仅当城市t还有他没吃过的狗粮，它到城市t之后就会立即品尝那一种狗粮，不会品尝该城市其他的狗粮(每到一个城市吃掉一种，可以多次到达)。

那么，请你为喵喵设计一个路线，使得它能品尝到尽量多种类的狗粮(以便回喵喵国改良猫粮)，并且最后会回到首都root，以便犬犬送它回家。

第一行一个数n，表示犬犬国的城市数

第二行n个数表示每个城市的狗粮种类

以下n-1行，每行2个数a,b，表示有一条路连接城市a,b

接下来一行一个数root，表示犬犬国的首都

一个数表示喵喵最多能吃到多少种狗粮

【友情提示】

一开始被传送到首都时，喵喵并不会品尝首都的狗粮，请注意最后要回到首都root

样例路线start>1>2(+)>1(+)>4(+)>1(+)>end

【数据约定】

设t为max{每个城市的狗粮种类}

30%数据满足n≤5，t≤5

60%数据满足n≤30，t≤30

100%数据满足n≤100000，0≤t≤2^31