Efficient Metro Reconstruction

In Stockholm, the metro system is outdated and inefficient. Due to changes in the city layout, some lines are overused while others remain nearly empty. In order to upgrade the system while minimizing interruptions, the city council has planned to rebuild the metro by replacing the current set of tracks with a new set.

The city’s metro network consists of N stations connected by N-1 tracks forming a tree (i.e. there is exactly one path between any two stations). The new plan is to use the same set of N stations but a different set of N-1 tracks, which also forms a tree.

However, during the reconstruction, only one track can be replaced per weekend. That is, every weekend one track is closed (removed) and a new track from the new plan is built, so that at all times the network has exactly N-1 tracks, keeping the network connected.

Your task is to design a replacement plan that meets these constraints while minimizing the number of weekends required. It can be proven that the minimum number of weekends needed is
\(\text{weeks} = (N-1) - |T_1 \cap T_2|\),
where \(T_1\) is the set of tracks in the current network and \(T_2\) is the set in the new plan. In other words, you only need to replace those tracks that are not common to both trees.

You are given the description of the two spanning trees. Output the minimum number of weekends needed to complete the replacement.

inputFormat

The first line contains an integer N (2 \(\leq\) N \(\leq\) 10⁵), the number of stations.

The next N-1 lines each contain two integers \(u\) and \(v\) (1 \(\leq\) u, v \(\leq\) N), describing a track in the current metro network.

The following N-1 lines each contain two integers \(u\) and \(v\) describing a track in the new metro plan.

It is guaranteed that both sets of tracks form a tree (i.e. they connect all stations without cycles).

outputFormat

Output a single integer representing the minimum number of weekends required to complete the reconstruction.

sample

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

2