Minimum Connected Subtree for Potion Production

In continent S, which is modeled as an unrooted tree with (n) vertices, each vertex contains a medicine with a positive integer attribute triple ((x,y,z)). A pharmacist can combine a set of medicines by choosing non‐negative real coefficients (a_i) (not all zero) to produce a potion with attribute ((\sum a_i x_i,; \sum a_i y_i,; \sum a_i z_i)).

Given a desired potion attribute ((a,b,c)), determine the minimum size of a connected subtree (i.e. a connected block of vertices) such that, by mixing all the medicines in that subtree with appropriate non‐negative coefficients, the resulting potion has exactly the attribute ((a,b,c)). If no such connected subtree exists, output (-1).

Note: Two or three medicines may be sufficient if the target vector lies in the cone spanned by their attribute vectors. By Carathéodory’s theorem, if ((a,b,c)) lies in the cone spanned by a set of vectors in (\mathbb{R}^3), then it can be expressed as a nonnegative linear combination of at most 3 of them.

inputFormat

The first line contains an integer (n), representing the number of vertices in the tree. Each of the next (n) lines contains three positive integers (x), (y), (z) denoting the medicine attribute at that vertex. Each of the following (n-1) lines contains two integers (u) and (v) indicating that there is an edge between vertices (u) and (v). The last line contains three positive integers (a), (b), (c) representing the desired potion’s attribute.

outputFormat

Output a single integer: the minimum number of vertices that need to be selected (forming a connected subtree) such that by mixing the corresponding medicines (with nonnegative coefficients, not all zero) one can obtain a potion with attribute ((a,b,c)). If no such connected subtree exists, output (-1).

sample

3
1 2 3
2 4 6
1 1 1
1 2
2 3
3 6 9

1