Arboriculture

Time limit1sMemory limit1024 MB

Summary

Match each of N target trees to a distinct ordered tree and cut branches so each becomes its target, minimizing the total number of cuts.

Level: Medium7 of 10
Topics: Tree, Dynamic programming, Graph
Solved: No attempts yet

Problem

In preparation for the Swedish Coding Cup Finals, the organizing committee is decorating the hall for the award ceremony with beautiful juniper trees. They have designed an arrangement of $N$ trees, each with a specific look. As the resident arborist of the competition, it is your job to fix the trees.

You ordered $M$ trees, and the shipment arrived a minute ago. You may not be able to pick $N$ trees that match the arrangement exactly. In that case, you must cut off some branches on some trees to change their looks into those required by the arrangement. The contest has just started, so you need to fix the trees right now, before the award ceremony.

Formally, a tree consists of a root, from which a number of branches (possibly none) extend. Each branch ends at a point called a vertex, from which any number of new branches can extend. Two trees look the same if they have the same structure of branches and vertices. The order in which branches grow from a vertex does not matter.

To change the layout of a tree, you can use your trusty lopper to cut off branches that grow from a vertex, one branch at a time. Branches can be cut from any part of the tree. Cutting a branch makes the whole subtree below it fall off. You want to finish as fast as possible. If you choose $N$ of the trees and cut them optimally, how many cuts do you need in total?

Input

The first line contains two integers $N$ ( $1 \le N \le 500$ ), the number of trees in the arrangement, and $M$ ( $N \le M \le 500$ ), the number of trees you ordered.

Then $N + M$ tree descriptions follow. First come the $N$ trees of the arrangement, followed by the $M$ ordered trees. A tree description starts with an integer $B \ge 0$ , the number of branches. The next line contains $B$ integers $a_1, a_2, \ldots, a_B$ , where $a_i < i$ . Each $a_i$ means that there is a branch between vertex $a_i$ and vertex $i$ . If a branch grows from the root, this number is $0$ .

There are at most $1000$ branches in total among the $N + M$ trees. It is guaranteed that the trees can be transformed in the described manner.

Output

Output a single integer: the minimum number of edges you must cut to transform the layouts of $N$ of the ordered trees into the layouts of the trees in the arrangement.

Hint

In the first sample, three trees are ordered and two trees need to be constructed. The second ordered tree exactly matches the first tree in the arrangement, so it can be chosen without any cuts. The third ordered tree is similar to the second tree in the arrangement, except it has an extra branch from the root. Thus, only one cut is needed to transform it.

Examples3

Example 1

Input

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

Expected output

Example 2

Input

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

Expected output

Example 3
Input
```
1 1
2 0 0
4 0 0 1 1
```
Expected output
```
2
```