Marshall Mathers, a magician (note the intellectual use of alliteration), code name "Houdini", is tasked distributing sour candy to his fans. His stock of sour candy can be modeled as a bunch of containers, $$$n$$$ of them to be precise. Container $$$i$$$ ($$$1 \leq i \leq n$$$) contains $$$a_i$$$ units of sour candy. Marshall by magic generates links from one container to another, in such a way that any container can be reached from any other container by traversing a serious of links, and this path is unique for all pairs of nodes. Further, at most one edge exists between 2 containers and no container has a link to itself (this whole setup is a tree).
He now wants to distribute the candy among his fans - he does this (magically) removing some of the links he created, splitting the tree into smaller trees, and giving each fan a tree of containers of sour candy. His supervisor Dr. Dre for reasons unknown wishes that each fan gets an even number of units of sour candy in total. Further, none of the candy should be left.
Marshall wants to know, if he removes links optimally, at most how many fans can he distribute candy to, if at all possible to satisfy the conditions set by Dr. Dre.
The first line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 200,000$$$), representing the number of containers.
The second line of input contains $$$n$$$ space-separated integers $$$a_1, a_2, ... a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).
The next $$$N-1$$$ lines contain to integers $$$1 \leq u \leq n$$$ and $$$1 \leq v \leq n$$$ representing a link between containers $$$u$$$ and $$$v$$$.
Output a single positive integer, representing the number of fans that Marshall can distribute sour candy to. Output $$$-1$$$ if it is impossible to satisfy Dr. Dre's conditions.
41 3 2 41 22 34 2
3
41 3 2 41 33 22 4
2
41 3 3 41 23 21 4
-1
In the first example, Houdini can remove the links 2-3 and 2-4 leaving the components (1,2), (3,) and (4,), each of which can be given to a fan.
In the second example, the link 2-4 can be removed, and this is the best we can do.
In the third example, there is no way to remove links such every tree has an even number of candies.
