Illuminating the Forest

An explorer duo is trying to light up a forest with bulbs. There are \( n \) bulbs numbered \(1, 2, \dots, n\). Two different trees are built on these bulbs:

• Tree A (red cords): Formed by \( n-1 \) red ropes connecting the bulbs, it is a tree.
• Tree B (blue cords): Formed by \( n-1 \) blue ropes connecting the bulbs, it is another tree.

Initially, all bulbs are off. We want to choose a subset of bulbs to turn on such that:

1. The bulbs turned on form a connected subgraph (a contiguous "block") in Tree A.
2. The bulbs turned on form a chain (i.e. a simple path) in Tree B. Note that a single bulb is considered a chain.

Determine the number of ways to choose such a subset. Throughout the problem, assume the trees are undirected and the unique simple path exists between any two bulbs in a tree.

Note: The time limit for this problem is 5 seconds.

inputFormat

The input is given as follows:

1. The first line contains an integer \( n \) denoting the number of bulbs.
2. The next \( n-1 \) lines each contain two integers \( u \) and \( v \) (1-indexed) representing an edge in Tree A.
3. The following \( n-1 \) lines each contain two integers \( u \) and \( v \) (1-indexed) representing an edge in Tree B.

outputFormat

Output a single integer — the number of valid ways to choose a subset of bulbs that satisfy the conditions.

sample

3
1 2
2 3
1 2
2 3

6