我们把 个点， 条边的连通无向图称为树。由若干个树组成的图称为森林。对于两个树 和 ，如果能够把树 的所有点重新标号，使得树 和树 完全相同，那么这两个树是同构的。也就是说，它们具有相同的形态。同样的，对于两个森林 和 ，如果能够把森林 的所有点重新标号，使得森林 和森林 完全相同，那么这两个森林是同构的。
琪露诺学习了有根树的树哈希（判断两个有根树是否同构的算法）后，她突发奇想，使用文言语言写了一个哈希函数，来判断两个无根森林是否同构。然而，你却看不懂文言语言，于是琪露诺又写了如下的伪代码，以此炫耀她天才般的算法。虽然，你一眼就看出来了，她不知道树的重心（能够加速判断无根树是否同构的性质）。
#include <bits/stdc++.h>
using namespace std ;
const int N = 1010 , mod = 4001 ;
struct graph
{
int n ;
bool edge[N][N] ;
} gg ;
int hash11( graph g )
{
int deg[N] ;
memset( deg , 0 , sizeof(deg) ) ;
for( int i = 0 ; i < g.n ; i ++ ) //这个for循环的功能是计算所有点的度数
{
for( int j = 0 ; j < g.n ; j ++ )
{
if( g.edge[i][j] )
{
deg[i] ++ ;
}
}
}
int a[N] , p[N] ;
memset( p , 0 , sizeof(p) ) ;
for( int i = 0 ; i < g.n ; i ++ )
{
a[i] = i ;
}
for( int i = 0 ; i < g.n ; i ++ ) //这个for循环的功能是对所有点按照度数进行冒泡排序
{
for( int j = g.n - 1 ; j > i ; j -- )
{
if( deg[a[j]] > deg[a[j - 1]] )
{
int tmp = a[j] ;
a[j] = a[j - 1] ;
a[j - 1] = tmp ;
}
}
}
int ans = 0 ;
for( int i = 0 ; i < g.n ; i ++ ) //这个for循环的功能是计算hash值
{
for( int j = 0 ; j < g.n ; j ++ )
{
if( g.edge[a[i]][j] )
{
ans += deg[a[i]] * deg[j] ;
deg[j] -- ;
ans %= mod ;
}
}
}
return ans ;
}
//以下省略main函数
var N , M : integer
N := 1000
M := 4001
// This function calculates the hash value.
// The variant edge means stores the graph:
// If the value of edge[i,j] is true, then it has an edge between i and j.
function hash11 ( edge [ 1 : N , 1 : N ] : boolean , n : integer )
begin
var deg [ 1 : N ] : integer
var i , j : integer
for i := 1 to n do
begin
deg [ i ] := 0
end
// This part calculates the degrees of all points
for i := 1 to n do
begin
for j := 1 to n do
begin
if edge [ i , j ] == true then do
begin
deg [ i ] := deg [ i ] + 1
end
end
end
var a [ 1 : N ] : integer
for i := 1 to n do
begin
a [ i ] := i
end
// This part is a bubble sort of all points by degree
for i := 1 to n - 1 do
begin
for j := n downto i + 1 do
begin
if deg [ a [ j ] ] > deg [ a [ j - 1 ] ] then do
begin
var tmp : integer
tmp := a [ j ]
a [ j ] := a [ j - 1 ]
a [ j - 1 ] := tmp
end
end
end
var ans : integer
ans := 0
// This part is to calculates the hash value.
for i := 1 to n do
begin
for j := 1 to n do
begin
if edge [ a [ i ] , j ] == true then do
begin
ans := ans + deg [ a [ i ] ] * deg [ j ]
deg [ j ] := deg [ j ] - 1
ans := ans mod M
end
end
end
return : ans
end
聪明的你显然已经发现了，这个函数既不能对于同构的森林给出相同的哈希值，又很容易给不同构的森林以相同的哈希值。
然鹅，最强的琪露诺显然不会轻易承认她的函数会出现问题。她试图通过给出特定的数据向拥有找出 bug 程度的能力的你证明这个函数是正确的。显然，让琪露诺记得森林的具体结构是一种奢望。她只告诉你了森林的结点个数和哈希值。
现在，你需要用程序给出一个与原森林不同构但是哈希值相同的森林向琪露诺证明她的函数极易产生哈希冲突。为了使琪露诺相信你给出的森林与她输入的森林不同，你给出的森林的结点个数必须与琪露诺给你的不同。
一行两个整数 和 ，分别代表琪露诺的森林的结点个数和哈希值。
第一行为一个整数 ，代表你给出的森林的结点个数。
随后 行 列为邻接矩阵表示的树，当且仅当点 和点 有边直接相连时，第 行第 列的数 为 。
5 12
9
0 1 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0
保证存在某个 个结点组成的森林哈希值为
你给出的森林结点个数必须不大于 ，且必须是合法的无根森林
数据保证有解