配点 : 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