布尔矩阵快速幂问题

题目描述

已经对开发计算矩阵乘法的高效算法进行了许多研究。但今天它仍然是一个棘手的话题。在这个问题中，您将计算平方布尔矩阵的 $2006$ 次方，其中加法和乘法定义如下：

布尔运算定义

设 $A$ 为方阵：

• $A$ 的零次方是单位矩阵
• $A$ 的第 $n$ 次方（$n > 0$）是 $A$ 与其 $(n − 1)$ 次方的乘积

输入输出格式

输入格式

输入包含多个测试用例：

1. 第 $1$ 行：两个整数 $K$ ($K < 1000$) 和 $M$ ($0 ≤ M ≤ 10K$)，表示矩阵维度为 $K × K$，矩阵有 $K + M$ 个 $1$
2. 第 $2$ 行 ~ 第 $M + 1$ 行：每行两个整数 $i$ 和 $j$ ($0 ≤ i, j < K$, $i ≠ j$)，表示矩阵第 $(i + 1)$ 行第 $(j + 1)$ 列元素为 $1$

注意：矩阵主对角线上的所有元素都是 $1$

输出格式

对于每个测试用例，输出一行，包含给定矩阵的 $2006$ 次方中 $1$ 的元素个数

示例

输入样例

3 4
1 2
2 1
0 1
0 2

输出样例

7

题目来源

$POJ$ 月刊--$2006.07.30$，$Static$