조명

밤이 되었는데 어린 파비얀은 어둠을 무서워한다. 설상가상으로 그의 방에 있는 샹들리에가 고장 났다.

샹들리에는 $n$개의 전구가 $n-1$개의 전선으로 연결되어 이루어져 있다. 각 전선은 두 전구를 잇고, 모든 전구는 직접 또는 다른 전구를 거쳐 서로 연결되어 있다. 즉, 샹들리에는 트리이다.

각 전구에는 상태를 바꾸는 버튼이 있다. 전구가 꺼져 있으면 버튼을 누를 때 켜지고, 켜져 있으면 꺼진다. 처음에는 일부 전구가 켜져 있고 일부는 꺼져 있다(모두 꺼져 있을 수도 있다). $n$개의 전구가 모두 켜져 있어야 파비얀이 무서움을 멈출 수 있다. 그래야 방이 충분히 밝아지기 때문이다.

파비얀은 전구의 수열을 하나 고른다. 수열에서 연속한 두 전구는 전선으로 직접 연결되어 있어야 한다. 전구는 수열에 여러 번 나와도 된다. 그는 수열에 나타나는 순서대로 전구를 방문한다. 파비얀은 버튼 누르기를 아주 좋아해서 전구든 세탁기든 엘리베이터든 가리지 않고 누른다. 전구를 방문할 때마다 그 전구의 버튼을 한 번 누르고, 상태가 바뀐다.

파비얀을 도와서, 마지막에 모든 전구가 켜져 있게 하는 가장 짧은 수열의 길이를 구하라. 처음에 꺼져 있는 전구가 적어도 하나 있다.

첫째 줄에 전구의 개수 $n$이 주어진다. 전구에는 $1$부터 $n$까지 번호가 붙어 있다.

둘째 줄에는 '0'과 '1'로만 이루어진 길이 $n$의 문자열이 주어진다. $i$번째 문자가 '0'이면 처음에 $i$번 전구가 꺼져 있고, '1'이면 켜져 있다.

이어지는 $n-1$개의 줄에는 전선으로 직접 연결된 두 전구의 번호 $x$, $y$ ($1 \le x, y \le n$)가 한 줄에 하나씩 주어진다.

마지막에 모든 전구가 켜져 있게 하는 수열의 최소 길이를 출력한다.

그런 수열은 항상 존재한다.

모든 서브태스크에서 $2 \le n \le 500\,000$을 만족한다.

첫 번째 예시에 대한 설명: 파비얀은 수열 1, 2, 3, 2를 고를 수 있다.