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 ≤ ai, bi ≤ 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.
E E E J J
Problem Author: Folklore (prepared by Sergey Pupyrev)
Problem Source: The 11th Urals Collegiate Programing Championship, Ekaterinburg, April 21, 2007