Problem Description

Xiao C is a pharmacist. To make a certain potion, she needs to find some herbs on the S Continent.

The S Continent can be modeled as an unrooted tree with $n$ vertices, and each vertex has one kind of herb. The property of each herb can be described by a triple $(x,y,z)$, where $x$, $y$, and $z$ are all positive integers.

If Xiao C obtains $n$ herbs with properties $(x_1,y_1,z_1), (x_2,y_2,z_2) \ldots (x_n,y_n,z_n)$, she may choose any $n$ non-negative real numbers $a_1,a_2 \ldots a_n$ that are not all $0$, and harmonize these herbs into a potion with properties $(\sum a_i x_i,\sum a_i y_i,\sum a_i z_i)$.

Now Xiao C needs to collect herbs on the S Continent. Specifically, she needs to choose a connected subgraph (a connected block) on the tree, and obtain all herbs on the vertices inside it. Given the desired potion property $(a,b,c)$, please find the minimum possible size of the connected block such that Xiao C can use the obtained herbs to harmonize a potion with property $(a,b,c)$.

Input Format

The input has $2n$ lines.

The first line contains four positive integers $n,a,b,c$.

The next $n$ lines each contain three positive integers $x_i,y_i,z_i$, representing the properties of the herb on node $i$.

The next $n-1$ lines each contain two integers $u$ and $v$, indicating that there is an edge connecting $u$ and $v$ in the tree.

It is guaranteed that the given edges form a tree.

It is guaranteed that there are no two completely identical herbs, but it is allowed that some herb has exactly the same property as the required potion.

It is guaranteed that for all herbs, $x_i + y_i + z_i = a + b + c$.

Output Format

Output one integer in a single line, the required answer.

4 2 2 3
1 1 5
3 2 2
3 3 1
2 4 1
1 2
2 3
2 4

3

8 3 269 1729
607 777 617
549 717 735
341 672 988
5 601 1395
846 263 892
796 954 251
243 144 1614
978 430 593
2 1
3 2
4 1
5 4
6 2
7 1
8 5

-1

Hint

Sample 1 Explanation

For the first sample, you can choose the connected block containing vertices $1$, $2$, and $3$, and take $a_1,a_2,a_3$ as $\dfrac{1}{2},0,\dfrac{1}{2}$ respectively. Then you can obtain a potion with properties $(\dfrac{1}{2} + \dfrac{3}{2},\dfrac{1}{2} + \dfrac{3}{2},\dfrac{5}{2} + \dfrac{1}{2}) = (2,2,3)$.

Subtasks

For all testdata, it is guaranteed that $1 \leq n \leq 5 \times 10^4$, $1 \leq a,b,c,x_i,y_i,z_i \leq 2 \times 10^9$.

• 2023.8.25 Added one set of hack data.

Translated by ChatGPT 5