安卓莎每天都要经过一个公园。他们之间的广场和小路看起来很无聊，所以他决定装饰他们。

公园由n个正方形组成，这些正方形与（n-1）条双向路径相连，这样任何正方形都可以通过这些路径从任何其他正方形到达。安卓莎决定在每个广场上挂一个彩色气球。气球的颜色由正整数来描述，从1开始。为了使公园色彩多变，安卓莎想用一种特殊的方式来选择颜色。更准确地说，他想使用这样的颜色，如果a，b和c是不同的正方形，a和b之间有一条直接的路径，b和c之间有一条直接的路径，那么这三个正方形上的气球颜色不能相同。

安卓莎希望尽量少用不同的颜色。帮他选颜色！

第一行输入一个整数n（3<=n<=2×10^5）表示正方形的数量。
接下来n-1行，每行包含两个整数x和y（1<=x，y<=n）表示x与y之间有一条连边。
保证了任何一个正方形都可以从任何其他路径到达。

第一行一个数,为最小颜色数.
接下来n个数,为[1,n]的点的颜色.

图论