K. Philadelphia Museum of Art
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The UTPC officers have arrived in Philadelphia, and have stumbled upon Kuroni and Tfg! They offered to help test the upcoming UTPC contest, but only if you solve their problem:

Kuroni and Tfg have arrived at the famous Philadelphia Museum of Art! On their map, they've marked the rooms they're most excited to see, from the grand Armor Court to the hidden Japanese Teahouse. Interestingly, the museum's layout is a tree, meaning it's possible to reach every room from the entrance and there are no cycles. Unfortunately, their time is limited, so they're unsure how to plan their route. Kuroni and Tfg each want to maximize their their own score, which is the number of rooms they had marked on their map that they ended up visiting.

To make things fair, they agree on the following rules:

  • They start together in room 1, the grand entrance, and always move together.
  • They take turns choosing which room to visit next, with Kuroni going first.
  • Once they visit a room, they can't return—there's too much to see!

When someone is choosing the next room, they will choose the room that maximizes their eventual final score. If there multiple such rooms, they will choose the rooms that maximizes the other's eventual final score. Given their preferences and the museum's layout, determine each of their scores!

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of rooms.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ is $$$1$$$ if Kuroni likes room $$$i$$$, and $$$0$$$ otherwise.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$, where $$$b_i$$$ is $$$1$$$ if Tfg likes room $$$i$$$, and $$$0$$$ otherwise.

The next $$$n-1$$$ lines each contain two integers $$$p$$$ and $$$q$$$ ($$$1 \le p,q \le n$$$), representing a connection between rooms $$$p$$$ and $$$q$$$ on the map. It is guaranteed that the edges form a tree.

Output

Output two integers $$$x$$$ and $$$y$$$ — the number of rooms Kuroni likes and the number of rooms Tfg likes, respectively, in the final route they take according to the rules.

Example
Input
5
0 1 1 0 1
0 0 1 1 1
1 2
1 3
2 4
2 5
Output
2 1
Note

In the sample, Kuroni will first choose to go from room $$$1$$$ to room $$$2$$$, visiting one of her marked rooms. Tfg will then go, choosing room $$$5$$$ so both of them visit a room they marked. Since they can't go back to room $$$2$$$ they are finished, with Kuroni visiting $$$2$$$ preferred rooms, and Tfg $$$1$$$.