9. 中心台站建设

【题目描述】

$n$ 个城市之间有通讯网络，从这 $n$ 个城镇中选定几座城镇，在那里建立中心台站，要求它们与其它各城镇相邻，同时为降低造价，要使中心台站数目最少。

【输入格式】

输入文件有若干行:

第一行，一个整数 $n$，表示共有 $n$ 个城市$(2 \leq n \leq 100)$

下面有 $n$ 行,每行有 $n$ 个数字。第 $p$ 行第 $q$ 列的数字表示城镇 $p$ 与城镇 $q$ 之间有无直接通讯线路。数字为 $1$ 表示有，$0$ 表示无。

【输出格式】

输出文件有若干行:

第一行，$1$个整数 $a$，表示最少中心台站数目。

第二行一个整数 $b$,表示共有 $b$ 种方案。下面有 $b$ 行，每行有 $a$ 个整数，表示一种建站方案。多种方案输出时，输出顺序按城镇编号由小到大字典序输出。

【样例输入1】

6
0 1 1 1 0 0
1 0 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1
0 0 1 0 0 1
0 0 0 1 1 0

【样例输出1】

2
5
1 5
1 6
2 5
3 4
4 5

【样例输入/输出2】

样例2