시계 트리

Farmer John의 새 헛간은 특이한 구조를 하고 있다. 헛간에는 방이 $N$개($2 \leq N \leq 2500$) 있고, 방은 $1 \ldots N$으로 번호가 매겨져 있다. 통로는 $N-1$개이며, 각 통로는 방 두 개를 연결한다. 어떤 방에서든 통로를 따라 다른 모든 방으로 이동할 수 있다.

헛간의 모든 방 벽에는 원형 시계가 걸려 있다. 문자판에는 표준 숫자 $1 \ldots 12$가 적혀 있다. 시계 바늘은 하나뿐이며, 항상 숫자 중 하나를 정확히 가리킨다. 두 숫자 사이를 가리키지는 않는다.

Bessie 소는 헛간의 모든 시계를 12를 가리키도록 맞추려고 한다. 다만 Bessie는 단순한 편이라서, 방에 들어설 때마다 그 방 시계의 바늘을 한 칸 앞으로 옮긴다. 예를 들어 5를 가리키는 시계는 6을 가리키게 되고, 12를 가리키는 시계는 1을 가리키게 된다. 같은 방에 여러 번 들어가면 들어갈 때마다 시계가 앞으로 간다.

Bessie가 모든 시계를 12로 맞출 수 있도록 걷기를 시작할 수 있는 방의 수를 구하라. Bessie는 시작한 방의 시계를 처음에는 옮기지 않지만, 그 방에 다시 들어올 때마다 옮긴다. 시계는 스스로 움직이지 않으며, Bessie가 방에 들어올 때만 움직인다. Bessie는 통로에 들어서면 반드시 반대쪽 끝으로 나와야 한다. 통로 중간까지만 들어갔다가 되돌아 나올 수는 없다.

첫 줄에 $N$이 주어진다. 다음 줄에는 각 방의 초기 시계 상태를 나타내는 정수 $N$개가 주어지며, 각 정수는 $1 \ldots 12$ 범위이다. 이어서 $N-1$개의 줄에 통로가 하나씩 주어진다. 각 줄에는 통로가 연결하는 두 방 번호 $a$와 $b$가 주어지며, 둘 다 $1 \ldots N$ 범위이다.

Bessie가 모든 시계를 12로 맞출 수 있는 출발 방의 수를 출력한다.

이 예제에서 Bessie는 방 2에서 출발할 때에만 모든 시계를 12로 맞출 수 있다. 예를 들어 방 1, 2, 3, 2, 4 순서로 이동하면 된다.