Subtree Isomorphism under Node Deletion

In this problem, you are given two rooted trees \(G\) and \(H\) satisfying \(1 \leq |H| \leq |G| \leq |H| + k\), where \(k\) is a small constant. The tree \(G\) is the "original" tree while \(H\) is the "target" tree. You are allowed to delete some nodes from \(G\) (except the root) so that the remaining nodes form a connected induced subgraph \(G'\) that:

• Contains the root of \(G\).
• Is isomorphic to \(H\). In other words, there exists a bijection between the nodes of \(G'\) and \(H\) which preserves the parent–child relationships and maps the root of \(G\) to the root of \(H\).

Note that if a node in \(G\) is chosen in \(G'\), then the unique path from the root of \(G\) to that node must also be entirely included in \(G'\). This forces the mapping to send every child of a node in \(H\) to an immediate child of the corresponding node in \(G'\>.

Your task is to decide whether there exists a way to delete nodes from \(G\) so that the resulting tree \(G'\) is isomorphic to \(H\).

Input and Output formats are described below.

inputFormat

The input consists of two parts describing the trees \(G\) and \(H\):

1. The first part describes tree \(G\):
   • An integer \(n\) (the number of nodes in \(G\)).
   • \(n-1\) lines each containing two integers \(u\) and \(v\), indicating that there is an edge from node \(u\) to node \(v\). It is guaranteed that node 1 is the root of \(G\).
2. The second part describes tree \(H\):
   • An integer \(m\) (the number of nodes in \(H\)).
   • \(m-1\) lines each containing two integers \(u\) and \(v\), indicating an edge from node \(u\) to node \(v\). Node 1 is the root of \(H\).

It is guaranteed that \(1 \leq m \leq n \leq m+k\) where \(k\) is a small constant.

outputFormat

Output a single line containing YES if there exists a way to delete nodes from \(G\) such that the remaining tree is isomorphic to \(H\); otherwise, output NO.

sample

1

1

YES