G - Graph Products Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100

くろうさ「グラフが複数与えられる問題で頂点数と辺数が横に並んでると切れ目がわかりにくくない? この革新的で親切なフォーマット,感謝してほしい」

しろうさ「サンプルの中身を親切にして」

問題文

この問題では,グラフは無向単純グラフのみを考える.グラフ H, H' に対し,グラフ H \mathbin{\square} H'H \times H' を以下のように定義する.H, H' の頂点集合をそれぞれ V(H), V(H') と書く.W = V(H) \times V(H') (すなわち「H の頂点と H' の頂点の組」全体の集合) とおく.

H \mathbin{\square} H' の頂点集合は W であり,H \mathbin{\square} H' において頂点 (u, u') \in W(v, v') \in W を結ぶ辺があるための必要十分条件は,以下のいずれかが成り立つことである:

  • u = v,かつ,H' において頂点 u' と頂点 v' を結ぶ辺がある.
  • u' = v',かつ,H において頂点 u と頂点 v を結ぶ辺がある.

H \times H' の頂点集合は W であり,H \times H' において頂点 (u, u') \in W(v, v') \in W を結ぶ辺があるための必要十分条件は,「H において頂点 u と頂点 v を結ぶ辺があり,かつ,H' において頂点 u' と頂点 v' を結ぶ辺があること」である.

K 個のグラフ G_1, \ldots, G_K が与えられる.各 k (1 \le k \le K) に対し,G_k の頂点集合は \{1, \ldots, N_k\} であり,G_kM_k 本の辺を持ちその i 番目 (1 \le i \le M_k) は頂点 A_{k,i}B_{k,i} を結ぶ.

k, k' (1 \le k \le K1 \le k' \le K) に対し,グラフ G_k \mathbin{\square} G_{k'}G_k \times G_{k'} が同型であるか判定せよ (すなわち,全単射 f\colon V(G_k) \times V(G_{k'}) \to V(G_k) \times V(G_{k'}) であって,任意の (u, u'), (v, v') \in V(G_k) \times V(G_{k'}) に対し「G_k \mathbin{\square} G_{k'} において頂点 (u, u') と頂点 (v, v') を結ぶ辺があること」と「G_k \times G_{k'} において頂点 f((u, u')) と頂点 f((v, v')) を結ぶ辺があること」が同値となるようなものが存在するか判定せよ).

制約

  • 1 \le K \le 10
  • 1 \le N_k \le 25\,000 (1 \le k \le K).
  • 0 \le M_k \le 25\,000 (1 \le k \le K).
  • 1 \le A_{k,i} < B_{k,i} \le N_k (1 \le k \le K1 \le i \le M_k).
  • 1 \le k \le K に対し,M_k 個の組 (A_{k,i}, B_{k,i}) (1 \le i \le M_k) はすべて異なる.

入力

入力は以下の形式で標準入力から与えられる.

K
N_1
M_1
A_{1,1} B_{1,1}
\vdots
A_{1,M_1} B_{1,M_1}
\vdots
N_K
M_K
A_{K,1} B_{K,1}
\vdots
A_{K,M_K} B_{K,M_K}

出力

出力は K 行からなり,各行は K 文字からなる.k 行目 (1 \le k \le K) の k' 文字目 (1 \le k' \le K) には,G_k \mathbin{\square} G_{k'}G_k \times G_{k'} が同型である場合は 1 を,同型でない場合は 0 を出力せよ.


入力例 1

5
3
2
1 2
2 3
4
3
1 2
2 3
3 4
5
5
1 2
1 3
2 4
3 5
2 3
8
6
1 2
5 8
1 6
4 8
2 7
6 7
6
9
1 3
3 5
1 5
1 2
2 3
3 4
4 5
5 6
1 6

出力例 1

00000
00000
00000
00000
00000