1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include<bits/stdc++.h>
using namespace std;


vector<vector<int>> GRAF;
vector<int> REVGRAF;
vector<int> DP;
vector<int> POP;
vector<vector<int>> LAYERS;
int il = 1;

int AM = 0;
int TotalAm = 0;
int NextIT = 0;


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int K, N; cin >> K >> N;
    POP.resize(1000007);
    GRAF.resize(N+1);
    REVGRAF.resize(N+1);
    DP.resize(N+1);
    LAYERS.push_back({});
    LAYERS.push_back({});
    for(int i = 1; i <= N; ++i){
        LAYERS[1].push_back(i);
    }
    for(int i = 2; i <= K; ++i){
        LAYERS.push_back({});
        int N2; cin >> N2;
        int next = GRAF.size();
        for(int l = 0; l < N2; ++l){
            int A; cin >> A;
            LAYERS[i].push_back(next+l);
            if(A == 0){
                GRAF.push_back({});
                REVGRAF.push_back(0);
                DP.push_back(0);
            }
            else{
                GRAF.push_back({});
                GRAF[il+A-1].push_back({next+l});
                POP[il+A-1]++;
                REVGRAF.push_back(il+A-1);     
                DP.push_back(0);   
            }
        }
        il = next;
        //cerr << i << "# " << flush;
    }
    //cerr << "git" << endl;
    queue<int> Q;
    for(int i = 1; i < GRAF.size(); ++i){
        if(POP[i] == 0){
            Q.push(i);
            DP[i]=1;
        }
    }
    //cerr << endl;
    while(!Q.empty()){
        int NODE = Q.front();
        //cerr << NODE << " ";
        if(REVGRAF[NODE] != 0){
            DP[REVGRAF[NODE]]+=DP[NODE];
            POP[REVGRAF[NODE]]--;
            if(POP[REVGRAF[NODE]] == 0){
                Q.push(REVGRAF[NODE]);
            }
        }
        Q.pop();
    }
    for(auto A : LAYERS){
        AM+=NextIT;
        NextIT=0;
        for(auto B : A){
            if(REVGRAF[B]==0){
                if(AM <= DP[B]){
                    TotalAm+=DP[B]-AM;
                    AM=0;
                }
                else{
                    AM-=DP[B];
                }
            }
            if(GRAF[B].size()==0){
                NextIT+=DP[B];
            }
        }
    }
    /*cerr << "\n";
    sleep(1);
    for(int i = 0; i < 3; ++i){
        cerr << ".";
        usleep(300000);
    }
    cerr << "\n";
    */
    cout << TotalAm;
}