Painted Corridors

The Institute of Colorfully Painted Corridors is planning the construction of a new building. The building has numerous junctions, and corridors that each connect a pair of junctions. The corridors will be painted by amazing new painting robots that drive along the corridors and paint all the walls as they go. The architect has specified the colors of some of the corridors, which may be red, orange, yellow, green, blue, or purple. However, there is only a budget for three painting robots, so there will be a single robot for each primary color (red, yellow, or blue). In addition, these robots are the cheapest possible version, and cannot turn their paint sprayer off (though they can go as fast or as slow as desired with no problems; they can even stop moving entirely).

If a corridor needs to be painted a secondary color (orange, green, or purple), in order for the paints to mix properly, the two robots with the appropriate primary colors must travel down the corridor in the same direction at the same time to create the correct color. The color mixing rules are: $orange = red + yellow$, $green = yellow + blue$, and $purple = red + blue$. A corridor that is unspecified in the plan may be painted any color, or left unpainted.

Corridors may be painted multiple times, provided that each time they are painted with the correct color. Corridors with no specified color can be painted multiple times with different colors. All corridors can be travelled along in both directions. The robots may end up at any junctions after painting all the corridors.

Given the architectâ€™s design, is it possible for the painting robots to paint the corridors the desired colors?

The first line of input contains five integers, $n$ ($2
\leq n \leq 100$), $m$ ($1
\leq m \leq \frac{n \cdot (n-1)}{2}$),

$r$, $b$ and $y$ ($1
\leq r, b, y \leq n$), where $n$ is the number of junctions,
$m$ is the number of
corridors, and $r$,
$b$ and $y$ are the initial junctions of the
red, blue, and yellow painting robots respectively. Junctions
are numbered $1$ through
$n$. Each of the next
$m$ lines contains two
integers $i$, $j$ ($1
\leq i < j \leq n$), and a single character
$c$ which is one of
`R`, `O`,
`Y`, `G`,
`B`, `P`,
`X`. The integers $i$, $j$ indicate that there is a corridor
between junction $i$ and
junction $j$, with
$c$ indicating the desired
color. (`R`, `O`, `Y`, `G`, `B`, `P`, `X`, corresponding
to Red, Orange, Yellow, Green, Blue, Purple, and Unspecified,
respectively.) There is at most one corridor between each pair
of junctions.

Output a single integer, $1$ if it is possible to paint the corridors as described and $0$ otherwise.

Sample Input 1 | Sample Output 1 |
---|---|

6 5 1 2 5 1 3 X 2 3 X 3 4 P 4 5 X 4 6 Y |
1 |

Sample Input 2 | Sample Output 2 |
---|---|

6 5 1 2 5 1 3 X 2 3 X 3 4 O 4 5 X 4 6 Y |
0 |

Sample Input 3 | Sample Output 3 |
---|---|

6 5 1 2 5 1 3 X 2 3 X 3 4 P 4 5 X 4 6 G |
1 |