Một chiến dịch lớn giữa các sinh viên ưu tú nhất khoa Công nghệ thông tin của một trường nào đó đã được khởi động, với mục tiêu là dựng lên một chương trình giả tưởng, biểu diễn một lượng rất lớn các biến cố có thể xảy ra từ các dữ kiện ban đầu, nhờ vào công nghệ $\text{AI}$. Tuy nhiên, việc dựng mô hình này sẽ rất, rất, rất, rất bất tiện. Thế nên, các bạn trẻ của chúng ta đã dựng nên một mô hình để mô phỏng lại quá trình dựng nên cây sự kiện.

Ban đầu, khi bắt đầu thiết lập, cây giả tưởng này chỉ có một nút duy nhất và một hàng nút duy nhất. Nút duy nhất đó được đánh số là nút $1$, ở hàng duy nhất được đánh số là $1$.

Có một thao tác dựng cây có thể được sử dụng. Thao tác này yêu cầu hai số nguyên không âm $a$, $b$ cho trước. Hai số này đảm bảo $a + b > 1$. Thao tác dựng cây như sau:

• Giả sử cây có tổng cộng $r$ hàng nút trước khi gọi thao tác này. Gọi $L=[L_1; L_2; L_3; ...; L_k]$ là số chỉ của các đỉnh ở hàng $r$. Hai số $a$ và $b$ này sẽ dựng các nút mới như sau:
  • Với nút $L_i$ $(1 \le i \le k)$, sinh ra tổng cộng $a + b$ nút mới làm con của nó. Giả sử cây hiện tại, lúc xét nút $L_i$ và trước khi thêm đỉnh, có tổng cộng $N$ nút. Các nút này sẽ lần lượt được đánh số từ $N + 1$ đến $N + (a + b)$.
  • Cũng tại bước sinh nút mới tại nút $L_i$ đang xét, các nút đã được đánh số $N + x$, với $1 \le x \le a$, cạnh nối giữa nút $L_i$ và nút $N + x$ được đánh dấu là cạnh $\text{"A"} + \text{str}(x)$ của nút $L_i$. Tiếp theo, các nút đã được đánh số $N + a + y$, với $1 \le y \le b$, có cạnh nối giữa nút $L_i$ và nút $N + y$ được đánh dấu là cạnh $\text{"B"} + \text{str}(y)$ của nút $L_i$.

Ví dụ, nếu gọi hai bước sinh nút mới lần lượt với hai bộ số $(a; b)$ là $(3; 2)$ và $(1; 1)$, ta có được cây sau:

Đôi khi, máy tính có thể gặp trục trắc, nên đôi khi thay vì sinh nút mới, máy tính sẽ kiểm tra bằng cách kiểm tra lại nút có chỉ số là $X$, bằng cách sử dụng các cạnh nào, để đi từ đỉnh của cây – nút $1$ – đến với nút có chỉ số là $X$, để đảm bảo rằng tiến trình sinh cây được chính xác. Cụ thể, để đi tới nút số $10$, trong ví dụ bên trên, ta sẽ từ nút $1$, sử dụng cạnh $\text{"A2"}$ của nút $1$ để đi xuống nút $3$; và từ nút $3$, ta sẽ sử dụng cạnh $\text{"B1"}$ của nút $3$ để đi xuống nút $10$. Chúng ta cần cho máy biết, các cạnh được sử dụng lần lượt là cạnh $\text{"A2"}$ và cạnh $\text{"B1"}$ (máy tính sẽ tự động biết cần dụng cạnh $\text{"Ax"}$ , hoặc cạnh $\text{"By"}$ của nút nào, nên việc thêm vào sử dụng cạnh đó của nút nào, trong trường hợp này, là không cần thiết).

Công trình được thiết lập cho một mục tiêu lớn hơn, nhưng trước hết thì đây là phiên bản thử nghiệm của công trình “Vẽ cây mô phỏng” lớn nhất từng được thực hiện. Hãy cùng thực hiện công tác thử nghiệm mô hình này nào.

Vì là mô hình thử nghiệm, nên trong suốt quá trình xử lí, tổng số nút mà máy tính cần phải xử lí sẽ không vượt quá $10^{18}$ nút.

4
1 1 1
1 1 1
2 2
2 3

1
A1
1
B1

4
1 1 1
1 1 1
2 1
2 4

0
2
A1 A1

9
1 1 1
1 1 1
2 1
2 2
2 3
2 4
2 5
2 6
2 7

0
1
A1
1
B1
2
A1 A1
2
A1 B1
2
B1 A1
2
B1 B1