E: えびちゃんを捕獲せよ

問題

あ　やせいの　えびちゃんが　とびだしてきた！

頂点数 $N$、辺数 $M$ の無向グラフで表されるフィールドがある。頂点は $1$ から $N$ まで、辺は $1$ から $M$ までで、それぞれ番号付けされている。また、各頂点には a から z の英小文字のいずれかが $1$ つ書かれている。

えびちゃんは任意の頂点に出現する可能性がある。 えびちゃんは、ある頂点に出現した後、すぐに別の頂点へワープして逃げてしまう。 えびちゃんは、次の条件をすべて満たすとき、頂点 $u$ から頂点 $v$ へワープすることができる。

• $u$ から $v$ へ、$K$ 本以下の辺を辿って移動できる。
• $u$ に書かれた文字と $v$ に書かれた文字が隣り合っている。
• 「英小文字 $c$ と隣り合っている文字」とは、英小文字のアルファベットを辞書順に並べ、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$ を双方向に結ぶことを意味する。

制約

• $2\leq N\leq 300$
• $1\leq M\leq N(N-1)/2$
• $1\leq K\leq 300$
• $c_i$ ($1\leq i\leq N$) は英小文字である。
• 多重辺および自己ループは存在しない。

出力形式

答えを一行に出力せよ。

入力例1

5 3 2
a b c d z
1 2
1 3
3 5

出力例1

2

えびちゃんがワープできる頂点の組は $(1, 2)$、$(1, 5)$、$(2, 3)$ であり、例として頂点 $2$ と頂点 $5$ に設置することで目標を達成することができる。また、$1$ 個以下の罠で目標を達成することはできない。なお、頂点 $4$ からはどこにもワープできないため、罠を設置する必要はないことに注意せよ。

入力例2

5 5 1
a b c d z
1 2
1 3
1 4
1 5
3 4

出力例2

2

えびちゃんがワープできる頂点の組は $(1, 2)$、$(1, 5)$、$(3, 4)$ であり、例として頂点 $1$ と頂点 $3$ に設置することで目標を達成することができる。このケースにおいても、$1$ 個以下の罠では目標を達成することはできない。

入力例3

4 6 3
h u p c
1 2
1 3
1 4
2 3
2 4
3 4

出力例3

0

えびちゃんはどの頂点間もワープできないので、罠を用意する必要はない。

---