Problem E
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?

Input

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

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

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

1

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

0

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

1