これでもう、怖くないよね。
ノアは世界的なストリートアーティストで、彼女の代名詞である蝶の絵は、特に美しいことで知られています。
今回、ノアはキャンバス に一枚の絵を描こうとしています。 は 個の頂点と 本の辺からなる無向単純連結グラフです。はじめ、キャンバスのどの頂点も赤く染まっていません。
上の図と同型な の部分グラフのうち、それを構成する 個の頂点がすべて赤く染まっているものをと呼びます。
1 行目に、グラフの頂点数 と辺数 が空白区切りで与えられる。
個の整数 を空白区切りで出力せよ。 は、 個の頂点が赤く染まった後にグラフに存在する赤い蝶の個数である。
すべての頂点が赤く染まると、 個の赤い蝶が存在します。
上の図は 個の頂点が赤く染まった状態を表しており、 個の赤い蝶が存在します。
すべての頂点は、あらかじめ決められた順序で赤く染まっていきます。頂点が赤く染まるたびに、キャンバスに描かれている赤い蝶の個数を求めてください。
単純グラフの定義
同じ頂点 と を結ぶ辺がなく、 頂点 を結ぶ辺が高々 本であるグラフを単純グラフといいます。
同型の定義
つのグラフ と の頂点間に全単射 が存在し、任意の に対して が成り立つとき、これらのグラフは同型であるといいます。つまり、頂点の番号を適切に付け替えることで、頂点と辺が完全に一致することを意味します。
部分グラフの定義
グラフ から、頂点の部分集合 と辺の部分集合 を選びます。 に属するすべての辺の両端点がともに に属するとき、グラフ を の部分グラフと呼びます。
続く 行のうち 行目に、 番目の辺が結ぶ つの頂点の番号 が空白区切りで与えられる。
次の行に、頂点が赤く染まる順序を表す長さ の順列 が空白区切りで与えられる。 は 番目に赤く染まる頂点の番号を表す。
入力で与えられるグラフは単純連結グラフであることが保証される。
