SOLVE

LATER

Isomorphic Trees

/

You are given two trees. You are allowed to perform an operation several times: attaching a new vertex connect to an existing vertex of a tree. For each vertex A of the first tree and vertex B of second tree, we root the first tree at A and the second tree at B then your task is to find the minimum number of operations needed to make two trees isomorphic.

(Two rooted trees are isomorphic if they are the same size \(N\), and there is a permutation \(P\) of \(\{1, 2, \dots, N\}\) such that P["root of the first tree"] = "root of the second tree" and there is an edge between \(u, v\) in the first tree iff there is an edge between \(P[u], P[v]\) in the second tree.)

**Input Format**

The first line contains two space-separated integers \(N, M\) denoting the number of vertices of two trees.

Each of \(N - 1\) next lines contains two space-separated integers \(u, v\) denoting an edge \((u, v)\) of the first tree.

Each of \(M - 1\) next lines contains two space-separated integers \(u, v\) denoting an edge \((u, v)\) of the second tree.

**Output Format**

Output \(N\) lines, each line contains \(M\) space-separated integers. \(j\)-th number in the \(i\)-th line contains the answer if we root the first tree at vertex \(i\) and the second tree at vertex \(j\).

**Constraints**

- \(1 \le N, M \le 50\).

Explanation

First tree:

Second tree:

- If we root the first tree at vertex \(1\) and the second tree at vertex \(1\), then we must attach a new vertex to vertex \(1\) in the first tree to make two trees isomorphic. The cost is \(1\).
- If we root the first tree at vertex \(1\) and the second tree at vertex \(2\), then we must attach two new vertcies to vertex \(2\) or \(3\) in the first tree and attach a new vertex to vertex \(2\) in the second tree to make two trees isomorphic. The cost is \(3\).

Time Limit:
3.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...