5. Cyklus v potrubí

Jedného dňa sa Marianka rozhodla osamostatniť a presťahovala sa do svojho vlastného bytu. Po pár dňoch bývania si uvedomila, že potrubie, ktoré vedie z jej záchoda, je pomerne opotrebované, a tak sa rozhodla ho vymeniť. Zavolala si majstrov z KSP (Komerční Smenári Potrubí) a tí jej ho bez meškania (rovnako ako robia všetky svoje povinnosti¹) prišli vymeniť. Dokonca za veľmi výhodnú cenu Marianke ponúkli nové špeciálne jednosmerné potrubia, cez ktoré síce dokáže voda tiecť iba jedným smerom, ale za to sú masívne rýchle. Aby bolo jasné, kto túto prácu vykonal, vyrezali logo KSP do niekoľkých častí potrubia. Po pár dňoch práce bolo nové potrubie hotové a Marianka si mohla spokojne nažívať ďalej. Lenže, hneď pri prvom použití záchoda Marianka zistila, že odtekanie vody zo záchoda nie je až tak masívne rýchle, ako majstri z KSP prezentovali. Sklamaná z výsledku práce si zavolala na pomoc Sama s jeho inšpekčnou kamerou do potrubia. Keď sa do potrubia pozreli, tak zistili, že KSP robotníci z potrubia pod záchodom urobili hotový labyrint. Marianka kontaktovala KSP aby zistila, že prečo potrubie vyzerá tak, ako vyzerá. Zodpovední zamestanci jej odpovedali, že je to preto, aby sa mohla voda, ktorá odtečie zo záchodu nekonečne veľa krát pozrieť na nejaké z KSP lôg, ktoré sú na stenách niektorých potrubí.

Marianke sa ale nezdalo, že by potrubie reálne malo túto vlastnosť a teda chcela, aby jej Samo pomohol zistiť, že či je to naozaj tak. Samo je ale zaneprázdnený rozbehávaním vecí, a tak Marianke nezostalo nič iné ako túto úlohu zveriť Vám. Pomohli by ste Marianke zistiť odpoveď, aby bola opäť šťastná?

Úloha

Vašou úlohou je určiť, či sa v potrubí nachádza taká postupnosť potrubí, ktorá obsahuje logo KSP a zároveň po nej voda vie chodiť donekonečna. Táto postupnosť musí začínať v záchode, ktorý sa nachádza na spojení potrubí číslo \(0\). Nezabudnite, že potrubie pod záchodom je špeciálne – voda cez potrubie vie tiecť iba jedným smerom.

Formát vstupu

Na prvom riadku vstupu sa nachádzajú dve medzerou oddelené čísla \(n, m\), kde \(n\) označuje počet spojení potrubí a \(m\) označuje počet potrubí. Spojenia potrubí sú očíslované číslami od \(0\) po \(n-1\). Nasleduje \(m\) riadkov, kde sa na každom riadku nachádzajú \(3\) medzerou oddelené údaje: čísla \(u, v, 0\leq u,v < n\) označujúce čísla spojení potrubí, medzi ktorými potrubie vedie a reťazec \(s, s \in \{\texttt{nic}, \texttt{KSP}\}\), ktorý označuje, či sa v danom potrubí nachádza logo KSP alebo nič. Je garantované, že medzi dvomi spojeniami potrubia nevedie potrubie jedným smerom viac ako raz.

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Vypíšte jediný riadok, ktorý obsahuje reťazec obsahuje v prípade, že systém potrubí obsahuje takú postupnosť potrubí, ktorá začína na spojení medzi potrubiami číslo \(0\), že voda môže donekonečna prechádzať okolo niektorého KSP loga. V opačnom prípade vypíšte reťazec NEobsahuje.

Príklady

Input:

3 3
0 1 KSP
1 2 nic
2 0 nic

Output:

obsahuje

Input:

3 3
0 1 KSP
1 2 nic
2 1 nic

Output:

NEobsahuje

Týmto potrubím síce môže voda prúdiť donekonečna, ale logo KSP vie vidieť iba raz.