회문

길이가 $n$인, 문자 0 또는 1로 이루어진 문자열이 주어진다. 문자에는 $1, 2, ..., n$의 번호가 붙어 있다. 처음에는 각 문자가 길이 1인 문자열 하나를 나타낸다.

연결은 두 단어 $a$와 $b$를 골라 지운 뒤, $b$의 문자가 $a$의 문자 뒤에 오도록 이어 붙인 문자열 $ab$로 바꾸는 연산이다.

$n$개의 초기 문자열은 $n-1$번의 연결을 거쳐 하나의 최종 문자열이 된다. $i$번째 연결은 $(a_i, b_i)$ 쌍으로 주어지며, $a_i$번째 문자가 속한 문자열과 $b_i$번째 문자가 속한 문자열을 잇는다는 뜻이다. $a_i$번째 문자와 $b_i$번째 문자는 같은 문자열에 속하지 않는다고 보장된다.

문자열 $w$의 회문 값은 $w$의 부분 문자열 가운데 회문인 것의 서로 다른 개수이다. 회문은 앞에서 읽든 뒤에서 읽든 같은 문자열이다. 부분 문자열은 문자열의 앞이나 뒤에서 문자를 0개 이상 지워서 얻는 문자열이다.

각 연결 후에 만들어진 문자열의 회문 값을 출력한다.

첫째 줄에 문자의 개수 $n$ ($1 \le n \le 100000$)이 주어진다.

둘째 줄에는 초기 문자열을 나타내는 $n$개의 0과 1로 이루어진 문자열이 주어진다.

이후 $n-1$개의 줄 각각에 $i$번째 연결을 나타내는 두 정수 $a_i$, $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$)가 주어진다.

$n-1$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 연결 후 얻은 단어의 회문 값을 출력한다.

세 번째 입력에서 연결할 때마다 새로 만들어지는 문자열은 차례로 00, 10, 00, 100, 1000, 001000, 00100010이다. 각각의 회문 값은 2, 2, 2, 3, 4, 6, 8이다.

예를 들어 00100010의 회문 값은 8이다. 이 문자열에는 회문인 부분 문자열이 8개 있다. 그것은 0, 00, 000, 10001, 0100010, 1, 010, 00100이다.