Problem G
経路

グラフとは、2つの頂点を結ぶ頂点と辺の集合からなる数学的構造です。頂点が$4$個で辺が$3$個のグラフの例を以下に説明します。

グラフの経路は、連続する頂点の間に辺がある$2$個以上の頂点に対する順序付きリストとして定義されます。 このタスクでは，同じ頂点が$2$回以上出現しない単純経路だけを扱います。 リストは順序を持つことに注意してください。例えば、“5-6-7”、“5-7-6”、“7-6-5”は全て異なる経路として扱います。

このタスクでは、グラフの各頂点には、$K$個の色のうちの$1$つを持っています。タスクは、経路内のどの$2$つの頂点も同じ色を持たない単純経路の数を見つけることです。

入力

入力の$1$行目には、$N$（頂点の数）、$M$（辺の数）、$K$（異なる色の数）の$3$つの整数が含まれています。

入力の$2$行目には、$1$から$K$までの整数$N$個が含まれています。これは、各頂点（頂点$1$から始まり、頂点$N$で終わります）の色を表します。

以降の$M$行は、それぞれ辺を表す$2$つの整数$a, b$ ($1 \le a, b \le N, a \neq b$)が含まれています。これは、辺で結ばれた$2$つの頂点を表します。どの$2$つの頂点の間にも、最大で$1$つの辺しか存在しません。

出力

$1$つの整数で、すべての頂点が別の色を持つ経路の数を出力します。この数は常に$10^{18}$より小さくなります。

制約

あなたのソリューションは、テストグループのセットでテストされ、それぞれのグループにポイントが定義されています。 各テストグループにはテストケースのセットが含まれています。 テストグループのポイントを得るためには、テストグループ内のすべてのテストケースが成功する必要があります。 あなたの最終的なスコアは、1回の提出での最大スコアとなります。

サンプル1の説明

最初の例のグラフは図のようになっており、各頂点は白（色$1$）、グレー（色$2$）、黒（色$3$）で塗りつぶされています。 全ての頂点が別の色を持つ経路は“1-2”、“2-1”、“2-3”、“3-2”、“2-4”、“4-2”、“1-2-4”、 “4-2-1”、“3-2-4”、“4-2-3”の$10$個あります。

注意: “1”は単一の頂点だけなので経路とならず、解に含みません。“1-2-3”は、色$1$を$2$個の頂点で含むため解に含みません。