#3579. 递增矩阵 暂未评定

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:无测试数据
上传者: luffy

题目描述

有一天,Alice在做作业时遇到了一些问题,现在她来寻求你的帮助。题目是这样的: 现在有两个n行m列的矩阵,如果一个矩阵是递增矩阵,那么它的每行(从左往右数)都是严格递增的,且每列(从上往下数)也是严格递增的。举个例子: 矩阵 9 10 11 12 13 14 是一个递增矩阵,因为它每行每列的数字都是严格递增的。 而矩阵 1 1 2 3 不是一个递增矩阵,因为它的第一行不是严格递增的。 现在,定义一个矩阵的第i行第j列的坐标为(i,j),你可以将第一个矩阵中位于坐标(i,j)的数字和第二个矩阵位于相同坐标的数字进行交换。最后,通过多次这样的操作(可以不操作)是否可以让题目给出的两个矩阵都为递增矩阵?如果可以,输出“Possible”,否则,输出“Impossible”(输出不包含引号)。

输入格式

第一行两个数n和m(1≤n,m≤50),表示两个矩阵的行数和列数。 接下来输入一个n行m列的矩阵,表示第一个矩阵。 再接着输入一个n行m列的矩阵,表示第二个矩阵。(1≤矩阵中每个数字≤10^9)

输出格式

如果可以通过多次操作使得两个矩阵都为递增矩阵,那么输出“Possible”,否则输出“Impossible”。

样例

样例输入 1

2 2
2 10
11 5
9 4
3 12

样例输出 1

Possible

样例输入 2

3 2
1 3
2 4
5 10
3 1
3 6
4 8

样例输出 2

Impossible