ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Classmates 3

Time limit: 1.0 second
Memory limit: 64 MB
Tanya (see problems Classmates and Classmates 2) has grown up and works as a computer science teacher at school. New Japanese software has been installed in her classroom recently. Now each computer can communicate with other computers in the classroom using a Japanese protocol or a European protocol and can switch between these protocols. When a computer gets a command to change protocol, it sends this command automatically to the computers to which it is connected and then switches itself immediately to the new protocol. Unfortunately, the protocols are incompatible, so a command to change protocol can be sent only to computers that use the same protocol as the computer that sends the command. Note that each of the computers that has received the command will send it back to the computer from which it was received, but that computer will not understand it because it will already use the new protocol.
At the start of a lesson Tanya has discovered that after the installation of the new software each computer was assigned at random one of the two available protocols. In order to conduct the lesson, Tanya has to switch all the computers to the same protocol as soon as possible.
Tanya can ask one of the pupils to change protocol at his or her computer, for example, from Japanese to European. Then this computer and all computers that use the Japanese protocol and are connected to that computer directly or via computers with the Japanese protocol will switch to the European protocol. All other computers will be unaffected. In the case when one of the computers is switched from the European protocol to the Japanese protocol, the result will be similar. Help Tanya to switch all the computers to the same protocol by means of the minimal number of requests to her pupils.


The first line contains the number of computers in the class N (1 ≤ N ≤ 50) and the number of connections between them M. In the next line there are N letters E or J. If the i-th computer is using the European protocol, then the i-th letter is E, otherwise it is J. The letters in the line are separated with a space. Each of the next M lines contains two different integers ai and bi (1 ≤ aibi ≤ N), which are the numbers of computers that have a direct connection. It is known that all computers in the class are connected to each other directly or via other computers.


In the first line output an integer K, which is the minimal number of requests to switch protocol that Tanya should make to her pupils in order to switch all the computers to the same protocol. Then output K lines describing the requests. A request to switch the i-th computer to the European protocol must be written as “i E”, and the request to switch it to the Japanese protocol must be written as “i J”. If there are several solutions, output any of them.


5 5
1 2
1 3
1 4
4 2
5 2
1 J
Problem Author: Folklore (prepared by Sergey Pupyrev)
Problem Source: The 11th Urals Collegiate Programing Championship, Ekaterinburg, April 21, 2007
To submit the solution for this problem go to the Problem set: 1544. Classmates 3