Description

He wants to build an ancient castle, where the roads inside form an unrooted tree. He wants to place the minimum number of soldiers on the tree’s nodes so that these soldiers can watch all the roads.

Note that when a soldier is on a node, all edges incident to that node can be watched.

Please write a program that, given a tree, helps Bob compute the minimum number of soldiers he needs to place.

Input Format

The first line contains an integer $n$, the number of nodes in the tree.

From the second line to the $(n+1)$-th line, each line describes one node’s information in the following order: an integer $i$, the label of this node; a natural number $k$, meaning there are $k$ undirected edges incident to node $i$; followed by $k$ integers, which are the labels of the other endpoints $r_1, r_2, \cdots, r_k$, indicating that there is one undirected edge between $i$ and each of these nodes.

For a tree with $n$ nodes, the node labels are between $0$ and $n-1$. In the input, each edge appears exactly once. It is guaranteed that the input describes a tree.

Output Format

Output a single integer, the minimum number of soldiers required.

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

1

Hint

Constraints

For all test points, $1 \leq n \leq 1500$.

Translated by ChatGPT 5