29877번 - LED-skeem 다국어

Valgusdiood (ingl light-emitting diode, LED) on elektroonikakomponent, mille kaht kontakti nimetatakse anoodiks ja katoodiks (alloleval joonisel vasakul vastavalt A ja K). Kui valgusdioodi anoodile rakendada kõrgem pinge kui katoodile (joonisel (a)), süttib diood põlema. Kui katoodil on kõrgem pinge kui anoodil (joonisel (b)), siis diood ei sütti, aga ei lähe ka rikki. Samuti ei sütti diood siis, kui selle anoodile ja katoodile rakendada võrdsed pinged (joonisel (c) ja (d)).

Jukul on hulk valgusdioode ja kontroller nende juhtimiseks. Kontrolleril on $N$ väljundit, mis on nummerdatud $1 \ldots N$. Kontrolleri igale väljundile saab programmiga rakendada kas kõrgema või madalama pinge (joonistel vastavalt 1 ja 0) ja niimoodi juhtida kontrolleri külge ühendatud valgusdioodide süttimist.

Juku tahab oma kontrolleri külge ühendada palju dioode nii, et iga dioodi oleks võimalik teistest eraldi sisse lülitada (s.t tekitada olukord, kus põleb ainult see diood). Näiteks alloleval joonisel vasakul kujutatud skeemis on võimalik kumbagi dioodi eraldi sisse lülitada, aga paremal kujutatud skeemis süttivad mõlemad dioodid alati korraga.

Kirjutada programm, mis saab Juku koostatud skeemi kirjelduse ja leiab, milliseid dioode on võimalik selle skeemiga teistest eraldi sisse lülitada.

Sisendi esimesel real on kontrolleri väljundite arv $N$ ($2 \le N \le 250$) ja dioodide arv $M$ ($1 \le M \le 25\,000$). Järgmisel $M$ real on igaühel kaks tühikuga eraldatud täisarvu $A_i$ ja $B_i$ ($1 \le A_i, B_i \le N$, $A_i \ne B_i$), mis näitavad, et $i$. dioodi anood on ühendatud kontrolleri väljundisse $A_i$ ja katood väljundisse $B_i$.

Väljastada üks rida iga dioodi kohta. Kui kontrolleri väljundid on võimalik pingestada nii, et põlema süttib ainult $i$. diood, väljasta $i$. reale 'JAH', vastasel juhul aga 'EI'.