← 返回题目列表

AtCoder · xmascon20_g

G. 图形产品

中文机器翻译题面 查看原题

配点 : 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_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)都是不同的。

入力

输入是按以下格式从标准输入给出的。

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