Hide

Problem G
経路

Languages de en et is ja lt lv no pl ru sv

グラフとは、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

23

$1 \le N, M \le 100, 1 \le K \le 4$

2

20

$1 \le N, M \le 300\, 000, 1 \le K \le 3$

3

27

$1 \le N, M \le 300\, 000, 1 \le K \le 4$

4

30

$1 \le N, M \le 100\, 000, 1 \le K \le 5$

サンプル1の説明

\includegraphics[width=5cm]{pathsfig.pdf}

最初の例のグラフは図のようになっており、各頂点は白(色$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$個の頂点で含むため解に含みません。