성호와 두산이

빨간색 구슬과 파란색 구슬이 각각 $N$개씩 있다. 성호와 두산이는 이 구슬을 가지고 게임을 한다. 먼저 게임을 시작하기 전에 구슬을 $N$개씩 나누어 가진다. 각자 나누어 가진 구슬을 정점으로 한 트리를 만들고, 루트가 될 구슬을 하나 정한다. 이 구슬이 1번이 된다.

게임은 성호부터 시작하며, 자신의 차례에는 다음과 같은 행동을 한다.

• 자신의 트리에서 리프인 구슬을 하나 제거한다. 자신의 트리에 제거할 구슬이 없다면 게임을 종료한다.
• 다음 차례는 제거한 구슬이 빨간색이라면 성호, 파란색이라면 두산이가 된다. 이 과정을 반복한다.

성호와 두산이가 만든 트리가 주어진다. 게임이 종료되었을 때 게임 전체에 남아 있는 구슬의 개수로 가능한 최솟값과 최댓값을 구하시오.

첫 번째 줄에 자연수 $N$이 주어진다.

두 번째 줄에 성호가 가져간 $N$개의 구슬의 색깔을 나타내는 정수가 공백으로 구분되어 주어진다. $i$번째 정수는 $i$번 구슬의 색깔을 나타내며, $0$은 빨간색, $1$은 파란색 구슬임을 의미한다. ($1 \leq i \leq N$)

세 번째 줄부터 $N-1$개의 줄에 걸쳐 성호가 만든 트리의 간선이 연결하는 구슬 번호 두 개가 공백으로 구분되어 주어진다.

$N+2$ 번째 줄에 두산이가 가져간 $N$개의 구슬의 색깔을 나타내는 정수가 공백으로 구분되어 주어진다. $i$번째 정수는 $i$번 구슬의 색깔을 나타내며, $0$은 빨간색, $1$은 파란색 구슬임을 의미한다. ($1 \leq i \leq N$)

$N+3$ 번째 줄부터 $N-1$개의 줄에 걸쳐 두산이가 만든 트리의 간선이 연결하는 구슬 번호 두 개가 공백으로 구분되어 주어진다.

게임이 종료되었을 때 게임 전체에 남아 있는 구슬의 개수로 가능한 최솟값과 최댓값을 공백으로 구분해 출력한다.

• $1 \leq N \leq 100,000$
• 빨간색 구슬이 총 $N$개 있고, 파란색 구슬이 총 $N$개 있다.
• 각자의 구슬 번호는 $1$부터 $N$까지이며, 서로 다르다.
• 성호와 두산이가 구슬을 연결한 간선은 각각 트리 구조를 이룬다.