# Overview

Atlassian Sourcetree is a free Git and Mercurial client for Windows.

Atlassian Sourcetree is a free Git and Mercurial client for Mac.

A school project to Advanced algorimithms subject. It is required really fast computing (under a few sec).

# 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

### Input

5 0 1 0 2 1 3 2 4 5 2 2 1 2 3 5 4 4 0

### Output

1 3

Example 1 is illustrated by trees A1, B1 in Image 1.

## Example 2

### Input

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

### Output

1 2 3 4

Example 2 is illustrated by trees A2, B2 in Image 1.

## Example 3

### Input

10 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 8

### Output

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.