5. Obedujeme koláčiky

Mačička a jej partia veľmi radi chodia do cukrárne. Keďže je ale partia veľmi veľká, tak sa tam nebaví každý s každým. Členovia, ktorý sa spolu bavia tvoria dvojice, ktoré voláme kamarátstva. Kamaráti sa spolu potom stretávajú pri koláčiku. V Kocúrkove sú presne dve cukrárne - jedna podáva iba ríbezľové koláče a druhá iba banánové koláče. Každý kamarát má samozrejme svoju preferenciu a je šťastný, iba ak idú do cukrárne, ktorá predáva jeho obľúbený koláč. V Kocúrkove sú všetci veľmi tvrdohlavý a nemajú radi zmenu. Preto každé kamarátstvo chodí, a aj vždy chodiť bude do tej istej cukrárne. Chodia tam dokonca aj vtedy, keď obaja kamaráti preferujú druhú príchuť koláčiku.

Kocúrkovo sa nevyhlo inflácií a chodiť na predražené koláčiky je v dnešnej dobe veľmi neekonomické. Mačička chce, aby jej partií ostali nejaké peniaze aj na spoločné výlety (napríklad na Mars, aj keď nevedia, čo stojí lístok) a povedala si, že takto to ďalej nepôjde. Dobre vie, že na to aby jej partia s \(n\) členmi zostala pokope je potrebných iba \(n-1\) kamarátstiev (partia je pokope, ak sa ľubovoľní dvaja členovia vedia skontaktovať buď priamo, alebo cez nejakých svojich kamarátov. Ako všetci dobre vieme, nemôžete napísať človeku, s ktorým nie ste kamarát). Mačičke nerobí problém pomôcť niektorým kamarátstvam aby sa rozpadli, ale chce, aby jej partia zostala pokope a všetci boli štastní. To znamená, že každému kamarátovi musí ostať aspoň jedno kamarátsvto, ktoré chodí do jeho obľúbenej cukrárne.

Úloha

Máme partiu o \(n\) členoch ktorá je pokope a \(m\) kamarátstiev. Každý člen má rád buď ríbezľové alebo banánové koláčiky. Každé kamarátstvo má dané, do ktorej z dvoch cukrární chodí. Pomôžte Mačičke nájsť \(n-1\) kamarátstiev, ktoré keď ostanú tak bude platiť, že skupina je pokope a každý člen má aspoň jedno kamarátstvo, ktoré chodí do jeho obľúbenej cukrárne alebo jej povedzte že sa to nedá.

Formát vstupu

V prvom riadku vstupu sú čísla \(n\) a \(m\) udávajúce veľkosť partie a počet kamarátstiev. Nasleduje \(m\) riadkov. Na \(i\)-tom riadku sú medzerou oddelené čísla \(a\), \(b\) (\(1 \leq a, b \leq n\)) určujúce indexy členov partie ktorý sa kamarátia a znak \(s\) (\(s\) ∈ {R, B}), ktorý určuje, do ktorej cukrárne chodia na koláčiky. Na poslednom riadku je string \(n\) znakov \(p\), \(p_j\) ∈ {R, B}, kde \(p_j\) je preferencia kamaráta \(j\).

Je zaručené, že v prvej a tretej sade kamarátstva nevytvárajú cyklus (teda pre ľobovolných dvoch členov partie platí, že ak sa chcú prostrednictvom kamarátstiev skontaktovať, tak existuje práve jedna možnosť ako to vedia docieliť).

Formát výstupu

Ak riešenie neexistuje, vypíš jeden riadok, na ktorom bude napísané Neda sa. Ak riešenie existuje vypíš medzerou oddelené \(i\) určujúce indexy kamarátstiev, ktoré ostali.

Príklad

Input:

3 3
1 2 R
1 3 B
2 3 B
RRB

Output:

3 1

Necháme tretie a prvé kamarátstvo. Správne riešenie by tiež bolo nechať druhé a prvé kamarátstvo.

Input:

3 4
1 2 R
1 2 B
1 3 B
2 3 B
RRR

Output:

Neda sa

Žiadne kamarátstvo 3 člena nechodí do cukrárne, kde predávajú ríbezľové koláčiky.