题目描述

シカの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$ の有向辺があることを意味する。 入出力例も参考にせよ。

题目大意

题目描述

给出一个$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$。

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$)
• 入力は全て整数