핸들 뭘로 하지

Baekjoon Online Judge를 비롯한 여러 온라인 채점 사이트에서는 각 유저를 고유한 ID로 구분한다. 이 ID는 핸들(Handle)이라고도 하며, 보통 여러 온라인 채점 사이트에서 동일하거나 비슷한 ID를 사용한다. 이러한 이유로 여러 사이트에서 활동하는 알고리즘 랭커들은 본명보다 핸들이 더 잘 알려지고는 한다.

알고리즘 최정상을 꿈꾸는 효규는 깊은 고민에 빠져있다. 바로 핸들을 정하는 일이다. 적당히 멋있으면서도 의미 있는 핸들을 원하지만, 도저히 떠오르지 않는다. 그 모습을 지켜보던 상원이는 주머니에 있던 트리 하나를 효규에게 주며 핸들 정하는 방법을 제안했다.

1. 트리는 $1$번부터 $N$번까지 총 $N$개의 정점으로 이뤄져 있으며, 각 정점에는 알파벳 소문자가 하나 적혀 있다.
2. $1$번 정점에서 시작한다.
3. 현재 정점에서 인접한 정점 중 아직 방문하지 않은 곳을 골라 이동한다. 이 과정을 더 이상 갈 수 없을 때까지 반복한다.
4. 방문한 정점 순으로 적혀있는 알파벳을 이어 붙인다.

이렇게 얻어지는 문자열을 효규의 핸들로 정한다. 하지만 얻을 수 있는 문자열의 종류가 너무 많기 때문에 그 중 사전상 가장 마지막에 오는 문자열을 핸들로 정하기로 했다. 상원이가 효규에게 준 트리의 정보가 주어졌을 때, 효규가 정할 핸들이 무엇인지 알아보자.

첫 번째 줄에 $N$이 주어진다. $(1 \le N \le 500\\,000)$

두 번째 줄에 각 정점에 적혀 있는 알파벳 소문자가 공백 없이 순서대로 주어진다.

세 번째 줄부터 $N-1$개의 줄에 두 정수 $u$, $v$가 공백으로 구분되어 주어진다. $u$번 정점과 $v$번 정점 사이 간선을 나타낸다. $(1 \le u, v \le N, u \neq v)$

효규가 정할 핸들을 출력한다.