TOI14: Technology

#include <bits/stdc++.h>
using namespace std;

enum checkStatus{
    unchecked = 0,
    checking = 1,
    checked = 2
};

const int N = 1e5;
const int K = 1e4;

vector<int> adj[N + 10];
vector<int> req[K + 10];
vector<checkStatus> sts(N + 10, unchecked);
int nTech, mxLv, limTime, currTime;
bool cycle;

void DFSInvent(int u){
    if(sts[u] == checked){
        return;
    }
    sts[u] = checking;
    for(int v : adj[u]){
        if(cycle || currTime > limTime){
            return;
        }
        if(sts[v] == unchecked){ // Invent required tech
            DFSInvent(v);
        } else if(sts[v] == checking){ // Found cycle
            cycle = true;
            return;
        }
    }
    ++currTime;
    sts[u] = checked;
    return;
}

int main(){

    scanf("%d %d %d", &nTech, &mxLv, &limTime);
    for(int i = 1; i <= nTech; ++i){
        int techLv, nPrev;
        scanf("%d %d", &techLv, &nPrev);
        req[techLv].push_back(i);
        for(int j = 1; j <= nPrev; ++j){
            int prev;
            scanf("%d", &prev);
            adj[i].push_back(prev);
        }
    }

    currTime = 0;
    cycle = false;
    int currLv = 0;
    for(int i = 1; i <= mxLv; ++i){
        for(int tech : req[i]){
            if(cycle || currTime > limTime){
                break;
            }
            DFSInvent(tech);
        }
        if(cycle || currTime > limTime){
            break;
        }
        ++currLv;
    }

    if(currLv == 0){
        cout << "-1";
    } else {
        cout << currLv;
    }

    return 0;
}