Snow Cleaning
Турнир за Купата на Декана, 2012
Time Limit: 0.1s, Memory Limit: 64MiB
Декември месец е. Прогнозите от месец насам са, че ще вали сняг, като сега, когато най-сетне това се случи, никой не беше изненадан. Освен "Столична Чистота", които, някак си, винаги са изненадани. Може би главно защото шефовете им са на Карибите с парите, отделени за почистването му. А там сняг рядко вали.

Ели, игнорирайки всеобщата паника, настанала покрай непроходимите улици, реши да вземе нещата в свои ръце. За целта, тя има малък спортен снегорин, с който е твърдо решена да разчисти всички улици в града.

За съжаление спортният снегорин не е толкова функционален, колкото обикновените такива. Той работи добре на равни улици, а също така ако се спуска по наклонена улица, но не и докато се изкачва нагоре. Затова момичето трябва да обхожда улиците по такъв начин, че никога да не се изкачва (като минава по изкачващите се улици в обратната посока).

Макар и благороден човек, Ели е решила да спести личните си пари от бензин, като минава по една улица точно по веднъж. Помогнете ѝ, като определите дали така тя може да изчисти всички улици в града, завършвайки обиколката си в началната си позиция. Ако да, също така намерете примерен път, който изпълнява дадените изисквания.
Вход
На първия ред на стандартния вход ще бъдат зададени две цели числа N и M, които отбелязват, съответно, броя кръстовища и броя улици. Следващите M реда ще съдържат по две цели числа Ai и Bi, указващи двете кръстовища, които съответната улица свързва, следвани от една главна латинска буква Si, указваща наклона ѝ. Si ще бъде 'U', за улица нагоре (uphill); 'D' за улица надолу (downhill); или 'E', за равна улица (even).

Възможно е да има повече от една улица между две кръстовища. Възможно е две различни улици между две кръстовища да имат различен наклон. Възможно е да има път от кръстовище до самото себе си. Възможно е да няма път между някои от кръстовищата. Ели винаги започва и завършва в кръстовище 1.
Изход
На първия ред на стандартния изход изведете "YES", ако Ели може да изчисти всички улици, минавайки по всяка от тях точно по веднъж, или "NO", в противен случай. Ако може, на следващия ред изведете разделени със шпации M + 1 цели числа - номерата на кръстовищата, в реда, в който ги минава Ели. Ако съществува повече от едно решение, изведете кое да е от тях.
Ограничения
  • 1 ≤ N ≤ 100
  • 1 ≤ M ≤ 1,000
  • 1 ≤ Ai, BiN
Примерен Вход Примерен Изход
3 3 1 2 D 2 3 D 3 1 D YES 1 2 3 1
3 3 1 2 D 2 3 U 3 1 U NO
5 8 5 4 D 5 4 U 1 2 D 1 5 E 5 2 E 4 2 E 2 3 E 3 4 E YES 1 2 5 4 3 2 4 5 1
В третия пример има две различни улици между кръстовища 4 и 5, при това с различен наклон.
Мрън!