Таня (см. задачи Одноклассники и Одноклассники 2) выросла, и теперь она работает учительницей информатики в школе. Недавно в её классе установили новое японское программное обеспечение. Теперь каждый компьютер может общаться с соседними компьютерами класса по одному из двух протоколов — японскому или европейскому — и может переключаться с одного протокола на другой. Получив команду на смену протокола, компьютер автоматически пересылает эту команду всем соседним компьютерам и тут же переключается сам. К сожалению, протоколы несовместимы. Настолько несовместимы, что даже простую команду на смену протокола смогут принять только те из соседей, которые работали в том же самом протоколе, что и компьютер, пославший команду. Заметьте, что каждый из соседних компьютеров отправит сигнал о смене протокола и пославшему сигнал компьютеру, но тот его уже не получит — ведь он уже переключился на новый протокол.

В начале занятия Таня обнаружила, что при установке нового программного обеспечения каждому компьютеру был случайным образом назначен один из двух доступных протоколов. Для проведения занятия Тане надо срочно перевести все компьютеры в один протокол.

Таня может попросить кого-то из своих учеников сменить протокол, например, с японского на европейский. Тогда его компьютер и все связанные с ним напрямую или через другие (но только работающие по японскому протоколу) компьютеры перейдут на европейский протокол. Остальные компьютеры, например, уже работавшие в европейском протоколе или просто не связанные с первым (напрямую или через другие компьютеры с японским протоколом), не будут менять свой протокол. Аналогичная картина будет, если на каком-то компьютере сделать смену с европейского на японский протокол. Помогите Тане переключить все компьютеры в какой-нибудь один протокол за минимальное количество обращений к ученикам.

В первой строке записаны числа N и M — число компьютеров в сети и число сетевых соединений между ними (1 ≤ N ≤ 50). В следующей строке через пробел записано N букв E или J. Если на i-м компьютере включен европейский протокол, то i-я буква будет E, если японский, — то J. Далее идут M строк, в каждой из которых находятся два различных числа a_i и b_i (1 ≤ a_i, b_i ≤ N) — номера компьютеров, соединенных сетью непосредственно. Известно, что с каждого компьютера можно через существующие сетевые соединения передать сообщение на любой.

В первой строке должно находиться число K — наименьшее число просьб о смене протокола, с которыми Таня должна обратиться к ученикам, чтобы сменить протокол всех компьютеров на какой-то один. Далее должны следовать K строк с описанием просьб. Просьба сменить протокол i-го компьютера на европейский записывается в виде «i E», на японский — «i J». Если существует несколько оптимальных решений, выведите любое из них.