Background

The testdata on Luogu are only for non-official exchange and are not official testdata. Official judging link: https://www.cspro.org/.

Recently, researchers at the Xixi Aifu Island Chemical Research Center carried out a chemistry outreach activity for junior high school students on the island. During the activity, they found that beginners in chemistry are very troubled by correctly balancing chemical equations. Some students even proposed some strange equations and asked the researchers to help balance them. Before balancing, the researchers first need to determine whether the equation can be balanced.

A chemical equation, also called a chemical reaction equation, is an expression of a chemical reaction using chemical formulas. The left and right sides of the equals sign list all reactants and products of the reaction, respectively. Each substance is represented by its chemical formula. A chemical formula lists the number of atoms of each element that make up the substance. For example, the chemical formula of water is $\text{H}_2\text{O}$, which means a water molecule contains two hydrogen atoms and one oxygen atom. In a chemical equation, each substance has a coefficient in front of its chemical formula, indicating the relative proportion of the amount of that substance participating in or produced by the reaction. For example, the equation $2\text{H}_2 + \text{O}_2 = 2\text{H}_2\text{O}$ means that two molecules of hydrogen react with one molecule of oxygen to produce two molecules of water. We say a chemical equation is balanced if, in the reactants and products of the equation, the total number of atoms of each element is equal. For example, in the above equation, the total numbers of hydrogen and oxygen atoms on the left are $4$ and $2$, and on the right are also $4$ and $2$, so the equation is balanced.

Problem Description

To balance a chemical equation, we can treat the coefficients of all substances in the equation as unknowns. Then, for each element involved, we write an equation in terms of these coefficients, forming a homogeneous linear system. Solving this system gives the coefficients of the substances. In this way, the problem of balancing a chemical equation is transformed into the problem of solving a homogeneous linear system. If the system has no non-zero solution, then the equation cannot be balanced. Otherwise, if the system has a non-zero solution, we may obtain a balanced equation. Of course, the final equation still needs to be checked using chemical knowledge; we will not consider that further here, and only consider whether a non-zero solution exists.

For example, to balance the chemical equation: $\text{Al}_2(\text{SO}_4)_3 + \text{NH}_3 \cdot \text{H}_2\text{O} \rightarrow \text{Al}(\text{OH})_3 + (\text{NH}_4)_2\text{SO}_4$

First, assume that all substances are on the same side of the equation (that is, we do not consider which are reactants and which are products). Let their coefficients be $x_1, x_2, x_3, x_4$. Then for each element that appears, we can write the following system of equations:

$$\begin{aligned} 2x_1 + 0x_2 + x_3 + 0x_4 &= 0 & \text{Al} \quad &(1) \\ 3x_1 + 0x_2 + 0x_3 + x_4 &= 0 & \text{S} \quad &(2) \\ 12x_1 + x_2 + 3x_3 + 4x_4 &= 0 & \text{O} \quad &(3) \\ 0x_1 + x_2 + 0x_3 + 2x_4 &= 0 & \text{N} \quad &(4) \\ 0x_1 + 5x_2 + 3x_3 + 8x_4 &= 0 & \text{H} \quad &(5) \end{aligned}$$

In matrix form:

$$\begin{pmatrix} 2 & 0 & 1 & 0 \\ 3 & 0 & 0 & 1 \\ 12 & 1 & 3 & 4 \\ 0 & 1 & 0 & 2 \\ 0 & 5 & 3 & 8 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \mathbf{0}$$

Perform Gaussian elimination on the coefficient matrix to obtain a row echelon form:

$$\begin{pmatrix} 2 & 0 & 1 & 0 \\ 0 & 1 & -3 & 4 \\ 0 & 0 & -\frac{3}{2} & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix}$$

Thus, the rank of the coefficient matrix is $3$. From linear algebra, we know that the dimension of the solution space of the homogeneous linear system $\mathbf{AX = 0}$ equals the number of unknowns minus the rank $\text{rank}\,\mathbf{A}$ of the coefficient matrix. To make the equation balance, we need the system to have a non-zero solution, which requires the dimension of the solution space to be greater than $0$, i.e., the rank of the coefficient matrix is less than the number of unknowns. Therefore, we can determine whether the equation can be balanced by checking whether the rank of the coefficient matrix is less than the number of unknowns. If it can be balanced, then the positions of reactants and products can be determined by the signs of the solution.

In this problem, we will be given some chemical equations. Please use the method above to determine whether they can be balanced. For easier processing in programs, the chemical formulas we use are simplified into strings containing only lowercase letters and digits, with no parentheses. Consecutive letters represent one element, and the following digits represent the number of atoms. When the number of atoms is $1$, the digit is not omitted. No element is repeated within a chemical formula. For example, the chemical formulas in the above equation can be simplified as: al2s3o12, n1h5o1, al1o3h3, n2h8s1o4.

Input Format

Read input from standard input.

The first line contains a positive integer $n$, indicating the number of chemical equations to be checked.

The next $n$ lines each describe one chemical equation to be balanced. Each line contains a positive integer and the chemical formulas of all involved substances, separated by spaces. The positive integer $m$ indicates the substances in the equation; the following $m$ strings give, in order, the chemical formulas of the reactants and the products in the equation.

Output Format

Write output to standard output.

The output contains $n$ lines. Each line contains the letter Y or N, indicating whether the given chemical equation to be balanced can be balanced by the method described in the statement.

6
2 o2 o3
3 c1o1 c1o2 o2
2 n2o4 n1o2
4 cu1 h1n1o3 cu1n2o6 h2o1
4 al2s3o12 n1h5o1 al1o3h3 n2h8s1o4
4 c1o1 c1o2 o2 h2o1

Y
Y
Y
N
Y
Y

Hint

Explanation of Sample 1

The input provides $5$ chemical equations to be balanced. Their balancing results are:

• $3\text{O}_2 = 2\text{O}_3$
• $2\text{CO} + \text{O}_2 = 2\text{CO}_2$
• $\text{N}_2\text{O}_4 = 2\text{NO}_2$
• It cannot be balanced because the product $\text{NO}$ or $\text{NO}_2$ is missing.
• $\text{Al}_2(\text{SO}_4)_3 + 6\text{NH}_3 \cdot \text{H}_2\text{O} = 2\text{Al}(\text{OH})_3 + 3(\text{NH}_4)_2\text{SO}_4$
• For $2\text{CO} + \text{O}_2 = 2\text{CO}_2$, after solving the corresponding linear system, the coefficient of $\text{H}_2\text{O}$ is $0$, meaning it does not participate in the reaction and is an extra substance. In this case, since the corresponding linear system has a non-zero solution, we still consider the equation to be balanceable.

Subtasks

For $20\%$ of the data, the number of substances in each equation does not exceed $2$, and the total number of elements involved in each equation does not exceed $2$.

For $60\%$ of the data, the number of substances in each equation does not exceed $3$, and the total number of elements involved in each equation does not exceed $3$.

For $100\%$ of the data, the number of substances in each equation does not exceed $40$, and the total number of elements involved in each equation does not exceed $40$. Also, $1 \le n \le 10$, and in each chemical formula, the number of atoms of each element does not exceed $50$.

Notes

• One method for Gaussian elimination on a matrix is:
  1. Examine the elements in the first column:
     • If all are zero, repeat the above check on the submatrix with this column removed.
     • If not all are zero, then:
       1. Examine the element in the first row and first column:
          • If it is $0$, swap this row with a later row whose first-column element is non-zero, so that the element in the first row and first column becomes non-zero.
       2. Subtract an appropriate multiple of the first row from each subsequent row so that the first-column elements of all subsequent rows become $0$.
  2. Repeat the above operations on the submatrix with the first row and first column removed until no submatrix remains.
• After performing Gaussian elimination on the coefficient matrix, the number of rows that are not all $0$ is the rank of the coefficient matrix.
• The judging environment provides only the standard libraries of each language. In particular, no linear algebra libraries are provided.

Translated by ChatGPT 5