Evolutionary Forest Similarity

Peter, a biologist, is comparing two evolutionary trees T₁ and T₂ on the same set of extant species \(\Sigma = \{1, 2, \ldots, n\}\). Each evolutionary tree is an undirected, unrooted tree whose leaves are labeled \(1,2,\ldots,n\) (representing extant species) while every internal (extinct) node has degree at least 3. For any subset \(X\subseteq \Sigma\) the evolutionary subtree \(T\{X\}\) is defined by:

1. For every pair of distinct points in \(X\) mark their simple path in \(T\) and delete any unmarked vertex not in \(X\) to obtain \(T'\).
2. Repeatedly delete any non‐leaf vertex \(v\) in \(T'\) with \(\deg(v)=2\) by merging its two incident edges, until no such vertex remains.

Removing a set of \(k\ge 0\) edges from an evolutionary tree yields \(k+1\) connected components. Taking the evolutionary subtree on the leaves in each connected component yields an evolutionary forest. Note that (i) the original tree is the forest obtained by removing no edge and (ii) if a component contains no extant species then its evolutionary subtree is defined to be empty.

Two evolutionary forests \(F_1\) and \(F_2\) (on the same extant species \(\Sigma\)) are defined to be similar if, after erasing the labels on the internal nodes, there exists a one‐to‐one correspondence \(\Phi\colon V(F_1)\to V(F_2)\) satisfying:

1. For any \(u\in \Sigma\), \(\Phi(u)=u\).
2. For any \(u,v\in V(F_1)\), \((u,v)\in E(F_1)\) if and only if \((\Phi(u),\Phi(v))\in E(F_2)\).

Now the difference number \(k^*\) of two evolutionary trees \(T_1\) and \(T_2\) is defined as the minimum nonnegative integer for which one can remove some set of \(k^*\) edges from each tree so that the derived evolutionary forests are similar. If \(T_1\) and \(T_2\) are already similar (when no edge is removed) then \(k^*=0\). Moreover, if \(1\le k^*\le k\) (an input upper‐bound), Peter wishes to know in how many ways one can choose the edge sets (one for each tree) so that the derived evolutionary forests are similar. Two removal methods are considered different if the edge set removed from \(T_1\) or \(T_2\) is different.

Your task is: Given two evolutionary trees \(T_1\) and \(T_2\) (each containing \(n\) extant species) and an integer upper bound \(k\), determine whether \(k^*\le k\). If yes, output YES on the first line. In addition, if \(1\le k^*\le k\) then on the next line output the total number of removal methods (i.e. the product of the number of ways on \(T_1\) and \(T_2\)) such that by removing exactly \(k^*\) edges from each tree the derived evolutionary forests are similar. If \(k^*>k\) then simply output NO.

Note: Two evolutionary trees are similar if and only if the pairwise distances between extant species (i.e. the leaves \(1,2,\ldots,n\)) are identical. Similarly, when a single edge is removed the forest consists of exactly two evolutionary subtrees whose structures are uniquely determined by the pairwise distances among the leaves in each connected component.

Input format:

n m1 m2 k
[Next m1-1 lines: two integers u and v denoting an edge in T1]
[Next m2-1 lines: two integers u and v denoting an edge in T2]

Here, in tree \(T_1\), vertices are numbered from 1 to m₁ and in tree \(T_2\), vertices are numbered from 1 to m₂. The extant species are exactly the vertices \(1,2,\ldots,n\> (which appear in both trees). It is guaranteed that each tree is valid and each internal node has degree at least 3.

Output format:

If k* ≤ k, output:
YES
[if k* ≥ 1, on the next line output the count of valid removal methods]
Otherwise, output:
NO

Example:

Test Case 1 (k*=0):

Input:
3 4 4 0
1 4
2 4
3 4
1 4
2 4
3 4
Output:
YES

</p>

Test Case 2 (k*=1):

Input:
4 6 6 1
1 5
2 5
5 6
3 6
4 6
2 5
5 6
3 6
4 6
1 6
Output:
YES
5

</p>

Test Case 3 (difference number > k):

Input:
3 4 5 0
1 4
2 4
3 4
1 4
2 4
4 5
3 5
Output:
NO

</p>

inputFormat

The input begins with a line containing four integers:
\(n\) \(m₁\) \(m₂\) \(k\) — where \(n\) is the number of extant species, \(m₁\) is the total number of nodes in \(T_1\), \(m₂\) is the total number of nodes in \(T_2\), and \(k\) is the allowed edge removal upper bound.

Then follow \(m₁ - 1\) lines, each containing two integers u v representing an edge in \(T_1\). This is followed by \(m₂ - 1\) lines, each containing two integers u v representing an edge in \(T_2\). In each tree, the vertices \(1,2,\ldots,n\) are the extant species (leaves).

outputFormat

If the minimum number of edges \(k^*\) to remove from each tree so that the resulting evolutionary forests are similar satisfies \(k^* \le k\), then print YES on the first line. Additionally, if \(k^*\ge 1\), print on the second line the total number of valid removal methods (the product of the number of edge removal choices for \(T_1\) and \(T_2\) yielding similar forests). Otherwise, print NO.

sample

3 4 4 0
1 4
2 4
3 4
1 4
2 4
3 4

YES

</p>