Inspection

Time limit1sMemory limit128 MB

Summary
Given a DAG representing ski slopes, find the minimum number of downhill paths needed to cover every edge, which reduces to a minimum path cover via bipartite matching.
Level

Medium7 of 10

Topics
Graph, DFS, Math
Solved
No attempts yet

Problem

You lead a team that inspects a newly built ski resort. The resort spans several mountains and is made up of a number of slopes. Slopes connect to one another, forking and joining, and the whole map is a directed acyclic graph: the vertices are points in the resort and every directed edge is a slope that always goes downhill.

Your team must inspect every slope. The lifts are not running yet, but you have a helicopter. On each flight the helicopter drops one inspector at any point of the resort. From that drop-off point the inspector skis downhill, inspecting every slope they ski down. A slope may be inspected more than once, but helicopter flights are expensive, so you must inspect all slopes using as few flights as possible.

Determine the minimum number of helicopter flights needed to inspect every slope.

Input

The first line contains a single integer nn (2≤n≤1002 \le n \le 100) — the number of points in the resort.

Each of the next nn lines describes one point, numbered from 11 to nn. The ii-th of these lines begins with an integer mim_i (0≤mi<n0 \le m_i < n), followed by mim_i distinct integers ai,1,…,ai,mia_{i,1}, \dots, a_{i,m_i} (1≤ai,j≤n1 \le a_{i,j} \le n, ai,j≠ia_{i,j} \ne i): there is a slope going downhill from point ii to point ai,ja_{i,j}.

Every point has at least one slope connected to it.

Output

Print a single integer — the minimum number of helicopter flights required to inspect all slopes.

Examples4

  1. Example 1

    Input
    8
    1 3
    1 7
    2 4 5
    1 8
    1 8
    0
    2 6 5
    0
    
    Expected output
    4
    
  2. Example 2

    Input
    2
    1 2
    0
    
    Expected output
    1
    
  3. Example 3

    Input
    3
    2 2 3
    0
    0
    
    Expected output
    2
    
  4. Example 4

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