There are \(n\) cities numbered from \(1\) to \(n\), and \(n-1\) roads connecting these \(n\) cities, i.e., it is a tree with \(n\) nodes. The task is to select as less cities as
you can to satisfy some constraints. A constraint is represented by three
numbers \(A,B\) and \(n_A\). This constraint means that if we
cut the road between city \(A\) and city \(B\) (we ensure the two cities are connected by a
road), the number of selected cities which can reach to city \(A\) is no less than \(n_A\). Please find the minimum number of
cities you should select to satisfy all constraints. If it is impossible to satisfy all constraints,
please print -1.
The first line contains an integer \(n(2\leq n\leq 200,000)\) which means the number of cities.
Then \(n-1\) lines follow. Each line contains two integers \(u,v(1\leq u,v\leq n)\) which means a road between city \(u\) and city \(v\).
Then one line contains an integer \(m(1\leq m \leq 400,000)\) which means the number of
constrains.
Then \(m\) lines follow. Each line contains three
integers \(A,B\) and \(n_A(0\leq n_A\leq 400,000)\) which describe the constraint (we
ensure there is a road between city \(A\) and city \(B\)).
Print the minimum number of cities you should select to satisfy all constraints. If it is impossible to satisfy all constraints, please print -1.