分数: 900 点
问题陈述
AtCoDeer 鹿想要一个满足以下条件的有向图:
- 顶点数, N,最多是 300.
- 不得存在自循环或多重边。
- 顶点编号为 1 通过 N.
- 每条边的权重介于 0 和 100 (含),或标签
XorY. - 对于每对两个整数 (x,y) 这样 1 ≤ x ≤ A, 1 ≤ y ≤ B,
距顶点的最短距离 S 到顶点 T 在图中,边缘标记为
X有重量 x 和标记的边缘Y有重量 y是 d_{x,y}.
构造这样一个图(以及一对 S 和 T) 给他,或者报告它不存在。 有关输出格式,请参阅输出部分。
约束
- 1 ≤ A,B ≤ 10
- 1 ≤ d_{x,y} ≤ 100 (1 ≤ x ≤ A, 1 ≤ y ≤ B)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
A B
d_{1,1} d_{1,2} .. d_{1,B}
d_{2,1} d_{2,2} .. d_{2,B}
:
d_{A,1} d_{A,2} .. d_{A,B}
输出
如果没有图形满足条件,则打印 Impossible.
如果存在满足条件的图,则打印 Possible 在第一行。
然后,在后续行中,按以下格式打印构造的图形:
N M u_1 v_1 c_1 u_2 v_2 c_2 : u_M v_M c_M S T
在这里, M 是边的数量,并且 u_i, v_i, c_i 表示边如下:有一条来自Vertex的边 u_i 到顶点 v_i 其重量或标签为 c_i.
另请参阅示例输出。
示例输入 1
2 3 1 2 2 1 2 3
示例输出 1
Possible 3 4 1 2 X 2 3 1 3 2 Y 1 3 Y 1 3
示例输入 2
1 3 100 50 1
示例输出 2
Impossible