## The Extra Node

View as PDF

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Given two trees and , the tree has nodes, numbered from to , while the tree has nodes, numbered from to . Bob found that if he removes one node from the tree , the two trees will have the same structure. Can you help Bob find the extra node in the tree ? If there are multiple nodes in the tree which can sastify the requirement, output the minimum one in tree .

#### Input Specification

The first line of input contains an integer ().

Each of the following lines contains two integers and (), indicating an edge in the tree .

Each of the following lines contains two integers and (), indicating an edge in the tree .

#### Output Specification

Output one integer, the index of the extra node in tree so that the two trees will be structurally identical after removing the extra node. If there are multiple answers, output the one with the minimum number in tree .

.
.

#### Sample Input

5
1 2
2 3
1 4
1 5
1 2
2 3
3 4
4 5
3 6

#### Sample Output

1