Seongho and Dusan

There are $N$ red marbles and $N$ blue marbles. Seongho and Dusan play a game with these marbles. Before the game starts, each of them takes $N$ marbles. Each player builds a tree whose vertices are the marbles they took, and picks one marble as the root. That marble becomes marble 1.

The game starts with Seongho. On each turn, the current player does the following.

• Removes one leaf marble from their own tree. If their tree has no marble left to remove, the game ends.
• The next turn belongs to Seongho if the removed marble was red, and to Dusan if it was blue. Repeat this process.

The first line contains the natural number $N$.

The second line contains $N$ integers separated by spaces, the colors of the marbles Seongho took. The $i$-th integer is the color of marble $i$, where $0$ means red and $1$ means blue. ($1 \leq i \leq N$)

The next $N-1$ lines, starting from the third line, each contain two marble numbers separated by a space. These are the edges of the tree Seongho built.

Line $N+2$ contains $N$ integers separated by spaces, the colors of the marbles Dusan took, in the same format as Seongho's colors.

The next $N-1$ lines, starting from line $N+3$, each contain two marble numbers separated by a space. These are the edges of the tree Dusan built.

Print the minimum and the maximum possible number of marbles remaining in the whole game when it ends, separated by a space.

• $1 \leq N \leq 100,000$
• There are $N$ red marbles and $N$ blue marbles in total.
• Each player's marble numbers run from 1 to $N$, and they are distinct from each other.
• The edges each player connected form a tree.