3723 - 修改01矩阵
Description

有一个 n*n 的 01 矩阵,每次操作可以选择一个位置改变这个位置元素的值(0变成1,1变成0),但是这个位置的上下左右四个位置的元素的状态也会发生改变(0变成1,1变成0)。问是否可以通过这个操作,将 01 矩阵所有元素都变成 0。操作次数不限,也可以为 0 次。

Input

第1行:一个整数 n(1 <= n <= 30),表示矩阵的边长。
接下来 n 行,每行 n 个整数(0 或 1),两个数之间用空格分开,表示初始矩阵。

Output

如果可以做到,输出 YES;否则输出 NO。

Examples

Input

3
1 1 1
1 0 1
1 1 1

Output

YES
Hint

这是经典的 Lights Out 问题。每个位置最多按一次(按两次抵消),设 n*n 个 0/1 变量表示是否按该位置。对每个格子列出"它最终变 0"的方程:它自身及上下左右被按的次数之和 ≡ 初始值 (mod 2)。得到一个 mod 2 意义下的线性方程组,用异或高斯消元判断是否有解:有解输出 YES,否则 NO。

Source
51nod
Tags
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 1
通过次数 1