問題文

クリスマスが終わったらツリーの片付けをしないといけません．

以下の問題を $Q$ 個のテストケースについて解いてください．

$N$ 頂点の木 $T$ が与えられます． 頂点には $1,\dots,N$ と番号がついており，$i$ 番目の辺は頂点 $u_i,v_i$ を結ぶ重み $w_i$ の辺です．

また $H$ 行 $W$ 列のグリッド $G$ があり，各マス目には白か黒の色が塗られています． $i$ 行 $j$ 列のマスの色の情報は文字 $S_{i,j}$ として与えられ，$S_{i,j}$ が . のとき白，$S_{i,j}$ が # のとき黒です． 塗り方は次の条件をすべて満たすことが保証されます．

• 黒いマスが $1$ つ以上存在する．
• 黒いマスは連結である．すなわち，任意の黒いマスから任意の黒いマスまで上下左右に隣接する黒いマスへの移動を繰り返すことで到達できる．
• 任意の黒いマス $X,Y$ について，$X$ から $Y$ まで上下左右に隣接する黒いマスへの移動を繰り返すことで移動する経路のうち，移動回数が最小であるものはただ一つ存在する．
• そのような移動経路に含まれるマス全体の集合を $P_{X,Y}$ で表す．特に $X,Y\in P_{X,Y}$ である．

次の条件をすべて満たすように $N$ 個の $G$ の黒いマス $C_1,\dots,C_N$ を選ぶことができるか判定し，可能なら選び方の一例を構築してください．

• 任意の $i,j\in\{1,\dots,N\}$ について，$T$ での頂点 $i,j$ 間の距離と $G$ での黒いマス $C_i,C_j$ 間の距離は一致する．
• $T$ での頂点 $i,j$ 間の距離は $i,j$ を結ぶ単純パス（ただ一つ存在する）に含まれる辺の重みの総和．
• $G$ での黒いマス $C_i,C_j$ 間の距離は $C_i$ から $C_j$ まで上下左右に隣接する黒いマスへの移動を繰り返して移動するときの移動回数の最小値，すなわち $|P_{C_i,C_j}|-1$．
• 任意の $G$ の黒いマス $C$ について，ある $i,j\in\{1,\dots,N\}$ が存在して $C \in P_{C_i,C_j}$．

入力

$Q$
$testcase_1$
$testcase_2$
$\ \vdots$
$testcase_Q$

$N$
$u_1\ v_1\ w_1$
$u_2\ v_2\ w_2$
$\ \vdots$
$u_{N-1}\ v_{N-1}\ w_{N-1}$
$H\ W$
$S_{1,1}S_{1,2}\cdots S_{1,W}$
$S_{2,1}S_{2,2}\cdots S_{2,W}$
$\ \vdots$
$S_{H,1}S_{H,2}\cdots S_{H,W}$

• $1\leq Q\leq 2024$
• $1\leq N\leq H\times W$
• $1\leq u_i\lt v_i\leq N$
• $1\leq w_i\leq H\times W$
• $1\leq H\leq 12$
• $1\leq W\leq 25$
• $S_{i,j}$ は . か #
• $S_{i,j}=$# であるような $i,j$ が存在する
• $S_{i,j}$ 以外の入力は全て整数である
• 各入力ファイルに対し，その入力に含まれるテストケースの $H\times W$ の総和は $12250$ 以下．

出力

それぞれのテストケースに対して順に以下のように出力してください．

問題文の条件を満たす選び方が存在しない場合は

No

Yes
$x_1\ y_1$
$x_2\ y_2$
$\vdots$
$x_N\ y_N$

サンプル

サンプル1

入力

5
4
1 2 1
1 4 1
1 3 2
3 3
#..
###
#..
4
1 2 1
1 4 2
1 3 2
3 3
#..
###
#..
3
1 2 1
1 3 2
3 3
#..
###
#..
15
4 15 1
8 13 5
5 12 2
8 14 2
3 14 4
4 10 2
7 10 3
1 8 5
9 12 2
6 14 4
10 14 2
4 11 1
8 12 2
2 10 3
9 9
...###...
..#.#.#..
..#####..
.#..#..#.
.#######.
#...#...#
#########
....#....
..#####..
20
5 15 10
11 14 10
6 16 8
3 10 7
12 17 10
11 19 2
7 11 12
3 16 2
1 12 9
5 13 10
2 7 16
9 15 10
5 18 3
4 16 7
2 15 3
12 18 4
6 14 8
3 20 8
8 14 4
12 25
#.....#.##.####.####.####
##...##..#....#....#.#...
.#...#...#.####.####.####
.##.##...#.#....#.......#
..#.#....#.####.####.####
..###....###..###..###..#
..#.#...................#
.##.##..#####.#####.#####
.#...#..#.#.#.#...#.#....
##...##.#.#.#.###.#.#####
#.....#.#.#.#.#...#.....#
#.....###.#.###...#######

出力

Yes
2 1
3 1
2 3
1 1
No
No
Yes
6 9
2 7
4 2
1 5
9 3
4 8
2 3
7 5
9 7
3 5
1 4
9 5
6 1
5 5
1 6
Yes
1 9
8 25
6 3
1 7
5 17
12 7
12 21
12 11
1 25
1 1
10 15
5 12
1 17
8 11
5 25
6 5
1 12
6 15
10 17
12 1

一つ目のテストケースに対する出力は次の図のようになっています．

二つ目のテストケースでは，問題文の一つ目の条件を満たすマスの選び方が存在しません．

三つ目のテストケースでは，問題文の一つ目の条件を満たすマスの選び方は存在しますがさらに二つ目の条件を満たすマスの選び方が存在しません．

四つ目のテストケースに対する出力は次の図のようになっています．

五つ目のテストケースに対する出力は次の図のようになっています．