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

[problemUrl]: https://atcoder.jp/contests/arc089/tasks/arc089_c シカのAtCoDeerくんは次のような条件を満たす有向グラフを欲しがっています。 - 頂点数$ N $は $ 300 $ 以下 - 自己ループや多重辺があってはいけない - 頂点には $ 1 $ から $ N $ の番号が付けられている - 各辺には $ 0 $ 以上 $ 100 $ 以下の整数値の重み、もしくは、`X` または `Y` というラベルが付けられている - 全ての $ 1\ <\ =\ x\ <\ =\ A $, $ 1\ <\ =\ y\ <\ =\ B $, を満たす整数の組 $ (x,y) $ に対し、 ラベル `X` が付けられた辺の重みを $ x $ に、 `Y` が付けられた辺の重みを $ y $ に書き換えたグラフの 頂点 $ S $ から $ T $ への最短距離は $ d_{x,y} $ AtCoDeerくんのためにこのようなグラフ(と $ S $ と $ T $ の組)をひとつ構成してください。条件を満たすグラフが存在しない場合はそれを指摘してください。 出力の方法については出力の欄を参照してください。

入力は以下の形式で標準入力から与えられる。 > $ 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` と出力せよ。 条件を満たすグラフが存在する場合、 $ 1 $ 行目に `Possible` と出力せよ。 $ 2 $行目以降に 構成したグラフを以下の形式で標準出力に出力せよ。 > $ 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 $ はグラフの辺を表す。 これは頂点 $ u_i $ から 頂点 $ v_i $ に 重み、あるいはラベル $ c_i $ の有向辺があることを意味する。 入出力例も参考にせよ。

2 3
1 2 2
1 2 3

Possible
3 4
1 2 X
2 3 1
3 2 Y
1 3 Y
1 3

1 3
100 50 1

Impossible

### 制約 - $ 1 $ $ <\ = $ $ A,B $ $ <\ = $ $ 10 $ - $ 1 $ $ <\ = $ $ d_{x,y} $ $ <\ = $ $ 100 $ ($ 1 $ $ <\ = $ $ x $ $ <\ = $ $ A $, $ 1 $ $ <\ = $ $ y $ $ <\ = $ $ B $) - 入力は全て整数