AT_jsc2026_final_b Binary Flood

$ N $ 頂点 $ M $ 辺の連結な単純無向二部グラフ $ G $ があります。 頂点には $ 1 $ から $ N $ までの番号が付いています。 $ i $ 本目の辺は頂点 $ U_i $ と頂点 $ V_i $ を結んでいます。 はじめ、各頂点は黒または白で塗られており、頂点 $ 1 $ は黒で塗られています。 また、各辺の両端の色は異なります。この条件から全ての頂点の色は一意に定まります。 以下の操作を何回でも行うことができます。 - 頂点 $ A_1,A_2,\ldots,A_K $ のうち $ 1 $ つを選び $ v $ とする。 $ G $ において $ v $ と同じ色の頂点からなる誘導部分グラフで、 $ v $ と同じ連結成分に属する全ての頂点について、白黒を反転する。 全ての頂点を同じ色にするために必要な操作回数の最小値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。 誘導部分グラフとは $ S $ をグラフ $ G $ の頂点の部分集合とします。このとき、 $ G $ の $ S $ による誘導部分グラフとは、頂点集合が $ S $ で、辺集合が「 $ G $ の辺であって両端が $ S $ に含まれるもの全て」であるようなグラフです。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ K $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_K $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_M $ $ V_M $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースの答えを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースでは、はじめ、頂点 $ 1,4 $ が黒、頂点 $ 2,3,5 $ が白で塗られています。 以下の手順で操作を行うと、 $ 2 $ 回の操作で全ての頂点を同じ色にすることができます。 - 頂点 $ 3 $ を選ぶ。頂点 $ 3 $ の色が黒に変わる。 - 頂点 $ 1 $ を選ぶ。頂点 $ 1,3,4 $ の色が白に変わる。 ### Constraints - $ 1 \le T \le 10^4 $ - $ 2 \le N \le 2 \times 10^5 $ - $ N-1 \le M \le 2 \times 10^5 $ - $ 1 \le K \le \min(N, 10) $ - $ 1 \le A_1 < A_2 < \ldots < A_K \le N $ - $ 1 \le U_i < V_i \le N $ - $ G $ は連結な単純無向二部グラフ - 全てのテストケースにおける $ N $ の総和は $ 2 \times 10^5 $ 以下 - 全てのテストケースにおける $ M $ の総和は $ 2 \times 10^5 $ 以下 - 入力される値は全て整数