C, D = map(int, input().split()) chodby = [] for i in range(C): chodba = list(map(int, input().split()))[1:] # zahodíme první číslo udávající délku chodby.append(chodba) # klice[i] je True, pokud máme klíč číslo i # Porotože klíče číslujeme od jedničky, potřebujeme pole délky D+1 # (použijeme indexy 1 až D, index 0 nepoužijeme) klice = [False] * (D+1) pozice = [0] * C # pozice[i] udává, kolik políček jsme už prozkoumali v i-té chodbě dolaru = 0 chodba_dveri = [-1] * (D+1) # chodba_dveri[i] udává číslo chodby, kde se nachází dveře druhu i prozkoumat = [] # seznam chodeb, které je třeba ještě prozkoumat # (místo fronty používáme zásobník, protože je to v Pythonu jednodušší; # pokud byste chtěli opravdu frontu, můžete použít collections.deque # ze standardní knihovny) for ch in range(C): prozkoumat.append(ch) # na začátku dáme do fronty všechny chodby while prozkoumat: # dokud seznam není prázdný cislo_chodby = prozkoumat.pop() # odeber ze začátku fronty chodba = chodby[cislo_chodby] while pozice[cislo_chodby] < len(chodba): policko = chodba[pozice[cislo_chodby]] if policko > 0: # dveře if not klice[policko]: # nemáme klíč # poznamenáme si, kde jsou dveře, abychom věděli, kam se vrátit, # až klíč najdeme chodba_dveri[policko] = cislo_chodby break # dál (zatím) nemůžeme if policko < 0: # klíč klice[-policko] = 1 if chodba_dveri[-policko] != -1: # už jsme potkali příslušné dveře? prozkoumat.append(chodba_dveri[-policko]) # vrátíme se k nim elif policko == 0: dolaru += 1 pozice[cislo_chodby] += 1 print(dolaru)