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 $ $