Tree isomorphism
The task
You are given two trees A and B. The tree A has N nodes, while the tree B has N+1 nodes. It is known that A has been created from B by removing one of its leaves, together with the adjacent edge. The task is to list each leaf of B which might be the removed one.
Image 1. All the leaves we are supposed to find are colored in red. Removing a red leaf of B1 or B2 results in a tree isomorphic with A1 or A2, respectively. |
Input
The first line contains an integer N representing the number of nodes of the tree A. Next, N−1 lines representing edges of A follow. Each line contains two indices (integers from 0,..,N−1) of directly connected nodes.
Finally, there are N lines that analogically represent edges of the tree B. In this case, indices of nodes are from 0,..,N.
Value of N is not greater than 1200.
Output
The output is formed by indices of those leaves of the tree B whose removal results in a tree isomorphic with the tree A. All the indices are in one line, separated by a space and written in ascending order.
Example 1
Input5 0 1 0 2 1 3 2 4 5 2 2 1 2 3 5 4 4 0Output
1 3Example 1 is illustrated by trees A1, B1 in Image 1.
Example 2
Input4 0 1 0 2 0 3 4 0 3 0 0 2 1 0Output
1 2 3 4Example 2 is illustrated by trees A2, B2 in Image 1.
Example 3
Input10 2 0 1 4 4 3 4 2 9 4 5 7 8 6 7 9 8 9 1 0 2 0 3 4 5 8 7 10 8 10 8 9 0 6 4 6 6 8Output
1 2
Public data
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set