あ やせいの えびちゃんが とびだしてきた!
頂点数 $N$、辺数 $M$ の無向グラフで表されるフィールドがある。頂点は $1$ から $N$ まで、辺は $1$ から $M$ までで、それぞれ番号付けされている。また、各頂点には a
から z
の英小文字のいずれかが $1$ つ書かれている。
えびちゃんは任意の頂点に出現する可能性がある。 えびちゃんは、ある頂点に出現した後、すぐに別の頂点へワープして逃げてしまう。 えびちゃんは、次の条件をすべて満たすとき、頂点 $u$ から頂点 $v$ へワープすることができる。
a
と z
をつなげて円環状に並べたものの中で $c$ と隣接している $2$ 文字を指す。たとえば、b
は a
と c
に隣り合っており、z
は y
と a
に隣り合っている。あなたは、いくつかの頂点に罠を設置して、えびちゃんを捕獲する体制を整えることにした。 えびちゃんは罠のある頂点に侵入すると、即座に捕まってしまう。
えびちゃんがどの頂点に現れたとしても身動きが取れないようにするために必要な罠の個数の最小値を求めよ。ただし、身動きが取れないとは、「現れた頂点に罠がある」または「罠のない頂点にワープできない」のいずれかが成り立つことを指す。
$N$ $M$ $K$ $c_1$ $c_2$ … $c_N$ $u_1$ $v_1$ … $u_M$ $v_M$
$1$ 行目には、頂点数 $N$、辺数 $M$、えびちゃんのワープに関する値 $K$ が与えられる。
$2$ 行目には、各頂点に書かれた文字がスペース区切りで与えられる。$c_i$ ($1\leq i\leq N$) は、$i$ 番目の頂点に書かれた文字を表す。
$2+i$ 行目 ($1\leq i\leq M$) には、$i$ 本目の辺の情報が与えられる。頂点 $u_i$ と $v_i$ を双方向に結ぶことを意味する。
答えを一行に出力せよ。
5 3 2 a b c d z 1 2 1 3 3 5
2
えびちゃんがワープできる頂点の組は $(1, 2)$、$(1, 5)$、$(2, 3)$ であり、例として頂点 $2$ と頂点 $5$ に設置することで目標を達成することができる。また、$1$ 個以下の罠で目標を達成することはできない。なお、頂点 $4$ からはどこにもワープできないため、罠を設置する必要はないことに注意せよ。
5 5 1 a b c d z 1 2 1 3 1 4 1 5 3 4
2
えびちゃんがワープできる頂点の組は $(1, 2)$、$(1, 5)$、$(3, 4)$ であり、例として頂点 $1$ と頂点 $3$ に設置することで目標を達成することができる。このケースにおいても、$1$ 個以下の罠では目標を達成することはできない。
4 6 3 h u p c 1 2 1 3 1 4 2 3 2 4 3 4
0
えびちゃんはどの頂点間もワープできないので、罠を用意する必要はない。