問題文

この問題では，グラフは無向単純グラフのみを考える．グラフ 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_k は M_k 本の辺を持ちその i 番目 (1 \le i \le M_k) は頂点 A_{k,i} と B_{k,i} を結ぶ．

各 k, k' (1 \le k \le K，1 \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 K，1 \le i \le M_k)．
• 各 1 \le k \le K に対し，M_k 個の組 (A_{k,i}, B_{k,i}) (1 \le i \le M_k) はすべて異なる．

入力例 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