通れない頂点が存在する閉路の総数（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

1, ..., n の番号がついた n 個の頂点とそれらをつなぐ枝からなる無向グラフを考えます。ただし、自己ループと多重辺は考えません。

隣接リストとある頂点 t と t を含まない頂点集合 S が与えられます。このとき、S の頂点を含まずに t を通過する閉路の総数を出力してください。ある閉路とその逆回りは区別しないため、注意してください。ただし、ここで頂点 t を通過する閉路とは、t を出発したあと t に戻ってくる経路で、同じ頂点を 2 回以上通らないもののことを言います。

入力される値

n t
k
s_1 ... s_k
v_1
a_{1,1} a_{1,2} ... a_{1,v_1}
v_2
a_{2,1} ... a_{2,v_2}
...
v_n
a_{n,1} ... a_{n,v_n}

・ 1 行目に、頂点の個数を表す整数 n と、通過点の頂点番号 t が与えられます。

・ 2 行目に、頂点集合 S の頂点数を表す k が与えられます。

・ 3 行目に、頂点集合 S の頂点が与えられます。

・ 2(i+1) 行目には頂点 i に隣接している頂点の個数が与えられ、 2(i+1)+1 行目には頂点 i に隣接している頂点の番号が半角スペース区切りで与えられます。(1 ≦ i ≦ n)

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 1 行で S の頂点を含まずに t を通過する閉路の総数を出力してください。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・ 3 ≦ n ≦ 12

・ 1 ≦ t ≦ n

・ 1 ≦ k ≦ n-2

・ 1 ≦ s_j < s_{j+1} ≦ n (1 ≦ j ≦ k-1)

・ s_j ≠ t (1 ≦ j ≦ k)
・ 1 ≦ v_i ≦ n-1 (1 ≦ i ≦ n)

・ 1 ≦ i ≦ n について

・ v_i = 1 のとき : 1 ≦ a_{i,1} ≦ n

・ v_i > 1 のとき : 1 ≦ a_{i,j} < a_{i,j+1} ≦ n (1 ≦ j ≦ (v_i)-1)

入力例1: 4 2
1
4
3
2 3 4
3
1 3 4
3
1 2 4
3
1 2 3

出力例1: 1

入力例2: 5 5
3
1 3 4
2
2 5
3
1 3 5
3
2 4 5
2
3 5
4
1 2 3 4

出力例2: 0

問題一覧へ戻る