← 返回题目列表

AtCoder · arc089_c

E. GraphXY 图

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

AtCoDeer 鹿想要一个满足以下条件的有向图:

  • 顶点数, N,最多是 300.
  • 不得存在自循环或多重边。
  • 顶点编号为 1 通过 N.
  • 每条边的权重介于 0 和 100 (含),或标签 X or Y.
  • 对于每对两个整数 (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