AT_arc089_c [ARC089E] GraphXY

题目描述

给出一个$A \times B$的矩阵,其中第$i$行第$j$列元素为$d_{i,j}$。试构造一个有向图,满足: 1、有向图点数$\leq 300$; 2、图中没有自环和重边; 3、图中边有边权,边权为 $[0,100]$ 中的整数,或者是未知数`X`或`Y`; 4、对于所有$x \in [1,A] , y \in[1,B]$,满足当未知数$X = x$,$Y = y$时,图中$S$到$T$的最短路为$d_{x,y}$。

输入格式

第一行两个正整数$A,B(1 \leq A , B \leq 10)$ 接下来一个$A \times B$的矩阵描述$d$。保证对于$\forall i \in [1,A] , j \in [1,B] , d_{i,j} \in [1,100]$

输出格式

如果不存在满足条件的有向图,输出一行`Impossible` 否则第一行输出`Possible`,第二行输出有向图的点数$n$和边数$m$,接下来$m$行每行输出$u,v,x$描述一条从$u$到$v$、边权为$x$的有向边,最后一行两个正整数$S,T$。

说明/提示

### 制約 - $ 1 $ $