Problem Statement

Once Christmas is over, the tree has to be put away.

Solve the following problem for $Q$ test cases.

You are given a tree $T$ with $N$ vertices. The vertices are numbered $1,\dots,N$, and the $i$-th edge connects vertices $u_i,v_i$ and has weight $w_i$.

There is also a grid $G$ with $H$ rows and $W$ columns, where each cell is painted white or black. The color of the cell in row $i$, column $j$ is given as a character $S_{i,j}$: the cell is white if $S_{i,j}$ is . and black if $S_{i,j}$ is #. The coloring is guaranteed to satisfy all of the following conditions.

• There is at least $1$ black cell.
• The black cells are connected. That is, any black cell can be reached from any black cell by repeatedly moving to a vertically or horizontally adjacent black cell.
• For any black cells $X,Y$, among the routes from $X$ to $Y$ made by repeatedly moving to a vertically or horizontally adjacent black cell, there is exactly one with the minimum number of moves.
• Let $P_{X,Y}$ denote the set of all cells contained in that route. In particular, $X,Y\in P_{X,Y}$.

Determine whether it is possible to choose $N$ black cells $C_1,\dots,C_N$ of $G$ so that all of the following conditions are satisfied, and if it is possible, construct one such choice.

• For any $i,j\in\{1,\dots,N\}$, the distance between vertices $i,j$ in $T$ equals the distance between black cells $C_i,C_j$ in $G$.
• The distance between vertices $i,j$ in $T$ is the sum of the weights of the edges on the simple path connecting $i,j$ (which is unique).
• The distance between black cells $C_i,C_j$ in $G$ is the minimum number of moves needed to travel from $C_i$ to $C_j$ by repeatedly moving to a vertically or horizontally adjacent black cell, that is, $|P_{C_i,C_j}|-1$.
• For any black cell $C$ of $G$, there exist $i,j\in\{1,\dots,N\}$ such that $C \in P_{C_i,C_j}$.

Input

$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}$ is . or #
• There exist $i,j$ such that $S_{i,j}=$#
• All inputs other than $S_{i,j}$ are integers
• For each input file, the sum of $H\times W$ over the test cases in that input is at most $12250$.

Output

For each test case, in order, output as follows.

If no choice satisfying the conditions in the problem statement exists, output only

No

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

Sample

Sample 1

Input

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
#.....#.##.####.####.####
##...##..#....#....#.#...
.#...#...#.####.####.####
.##.##...#.#....#.......#
..#.#....#.####.####.####
..###....###..###..###..#
..#.#...................#
.##.##..#####.#####.#####
.#...#..#.#.#.#...#.#....
##...##.#.#.#.###.#.#####
#.....#.#.#.#.#...#.....#
#.....###.#.###...#######

Output

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

The output for the first test case is illustrated in the figure below.

In the second test case, there is no choice of cells satisfying the first condition in the problem statement.

In the third test case, there are choices of cells satisfying the first condition in the problem statement, but none of them also satisfies the second condition.

The output for the fourth test case is illustrated in the figure below.

The output for the fifth test case is illustrated in the figure below.