USACO 2023 - US Open - Hạng Vàng

Vì sự thiếu tổ chức trong cấu trúc của hệ thống mootel (hệ thống nhà nghỉ mới nhưng ưu tiên các chú trâu/bò), nông dân John quyết định trở thành người bảo quản mootel nhằm khôi phục lại trật tự giữa các chuồng.

Mỗi mootel có \(N\) chuồng được đánh số từ \(1\) đến \(N\) \((1 \le N \le 10^5)\) và có \(M\) \((1 \le M \le 10^5)\) hành lang hai chiều nối giữa các cặp chuồng với nhau. Chuồng \(i\) được sơn màu \(C_i\) và ban đầu có một chiếc chìa khoá màu \(S_i\) ở bên trong. Bác John cần sắp xếp lại những chiếc chìa khoá này nhằm xoa dịu những chú bò và khôi phục lại trật tự giữa các chuồng.
Bác John bắt đầu ở chuồng \(1\), không cầm chiếc chìa khoá nào và được phép thực hiện một trong các hành động sau:

• Nhặt một chiếc chìa khoá trong chuồng mà hiện tại bác đang đứng. Bác John có thể giữ nhiều chìa khoá cùng lúc.
• Đặt một chiếc chìa khoá trong tay xuống chuồng hiện tại. Một chiếc chuồng có thể để nhiều chìa khoá.
• Trở về chuồng \(1\) thông qua các hành lang.
• Đi đến một chuồng khác chuồng \(1\) thông qua các hành lang. Bác John chỉ có thể đi đến các chuồng mà có màu trùng với màu của một chiếc chìa khoá mà bác John đang cầm trên tay.

Không may thay, dường như những chiếc chìa khoá đang không ở vị trí dự định của nó. Để khôi phục lại trật tự cho các mootel của mình, bác John cần đặt chiếc chìa khoá màu \(F_i\) bên trong chuồng thứ \(i\). Dữ liệu đảm bảo rằng \(S\) là một hoán vị của \(F\).

Cho \(T\) \((1 \le T \le 100)\) mootel khác nhau, bác John bắt đầu từ chuồng \(1\) và cần đặt những chiếc chìa khoá vào vị trí thích hợp của nó và kết thúc ở chuồng \(1\). Với mỗi mootel, kiểm tra xem liệu bác John có thể tái cấu trúc trật tự cho nó không.

Input

• Dòng đầu chứa số \(T\).
• Mỗi test sẽ cách nhau bởi một dòng trống. Dòng đầu tiên của mỗi test sẽ gồm hai số \(N, M\).
• Dòng thứ hai của mỗi test gồm \(N\) số \(C_i\) \((1 \le C_i \le N)\).
• Dòng thứ ba của mỗi test gồm \(N\) số \(S_i\) \((1 \le S_i \le N)\).
• Dòng thứ tư của mỗi test gồm \(N\) số \(F_i\) \((1 \le F_i \le N)\).
• \(M\) dòng tiếp theo của mỗi test sẽ gồm \(2\) số khác nhau \(u_i\) và \(v_i\) \((1 \le u_i, v_i \le N)\), nghĩa là có một hành lang hai chiều nối giữa chuồng \(u_i\) và chuồng \(v_i\). Không có hai hành lang nào giống nhau.

Tổng của \(N\) giữa các test không quá \(10^5\), tổng của \(M\) giữa các test không quá \(2 \times 10^5\).

Output

• Gồm \(T\) dòng, mỗi dòng ghi chữ "YES" hoặc "NO" (không bao gồm dấu nháy kép) cho biết bác John có thể đặt lại các chìa khoá màu \(F_i\) vào chuồng \(i\) hay không.

Scoring

• Subtask \(1\): \(N, M \le 8\).
• Subtask \(2\): \(C_i = F_i\) \(\forall i \in [1, n]\).
• Subtask \(3\): Không có ràng buộc gì thêm.

2

5 5
4 3 2 4 3
3 4 3 4 2
2 3 4 4 3
1 2
2 3
3 1
4 1
4 5

4 3
3 2 4 1
2 3 4 4
4 2 3 4
4 2
4 1
4 3

YES
NO

- Chuồng hiện tại: $1$. Chìa khoá đang cầm: []. Chìa khoá trong chuồng: [3, 4, 3, 4, 2].
(nhặt chìa khoá màu $3$).
- Chuồng hiện tại: $1$. Chìa khoá đang cầm: [3]. Chìa khoá trong chuồng: [x, 4, 3, 4, 2].
(di chuyển từ chuồng $1 \rightarrow 2$, bước đi này hợp lệ vì đang có chìa khoá màu $C_2 = 3$).
- Chuồng hiện tại: $2$. Chìa khoá đang cầm: [3]. Chìa khoá trong chuồng: [x, 4, 3, 4, 2].
(nhặt chìa khoá màu $4$).
- Chuồng hiện tại: $2$. Chìa khoá đang cầm: [3, 4]. Chìa khoá trong chuồng: [x, x, 3, 4, 2].
(di chuyển từ chuồng $2 \rightarrow 1 \rightarrow 4 \rightarrow 5$, hợp lệ vì đang có chìa khoá màu $C_4 = 4$ và $C_5 = 3$).
- Chuồng hiện tại: $5$. Chìa khoá đang cầm: [3, 4]. Chìa khoá trong chuồng: [x, x, 3, 4, 2].
(nhặt chìa khoá màu $2$ và đặt chìa khoá màu $3$ xuống).
- Chuồng hiện tại: $5$. Chìa khoá đang cầm: [2, 4]. Chìa khoá trong chuồng: [x, x, 3, 4, 3].
(di chuyển từ chuồng $5 \rightarrow 4 \rightarrow 1 \rightarrow 3$, hợp lệ vì đang có chìa khoá màu $C_4 = 4$ và $C_3 = 2$).
- Chuồng hiện tại: $3$. Chìa khoá đang cầm: [2, 4]. Chìa khoá trong chuồng: [x, x, 3, 4, 3].
(nhặt chìa khoá màu $3$ và đặt chìa khoá màu $4$ xuống).
- Chuồng hiện tại: $3$. Chìa khoá đang cầm: [2, 3]. Chìa khoá trong chuồng: [x, x, 4, 4, 3].
(di chuyển từ chuồng $3 \rightarrow 2$ và đặt chìa khoá màu $3$ xuống).
- Chuồng hiện tại: $2$. Chìa khoá đang cầm: [2]. Chìa khoá trong chuồng: [x, 3, 4, 4, 3].
(di chuyển từ chuồng $2 \rightarrow 1$ và đặt chìa khoá màu $2$ xuống).
- Chuồng hiện tại: $1$. Chìa khoá đang cầm: []. Chìa khoá trong chuồng: [2, 3, 4, 4, 3].

5

2 0
1 2
2 2
2 2

2 1
1 1
2 1
2 1
1 2

2 1
1 1
2 1
1 2
1 2

2 1
1 1
1 2
2 1
1 2

5 4
1 2 3 4 4
2 3 5 4 2
5 3 2 4 2
1 2
1 3
1 4
4 5

YES
YES
NO
YES
NO

Pareidolia là một hội chứng mà mắt bạn có xu hướng nhìn thấy những thứ quen thuộc trong ảnh mà thậm chí không tồn tại (ví dụ như thấy một gương mặt trên đám mây). Nông dân John, một người với niềm yêu thương những chú bò của mình, thường xuyên thấy những thứ liên quan đến bò trong mọi vật dụng. Ví dụ, nếu như bác John thấy xâu "bqessiyexbesszieb", đôi mắt của bác sẽ tự động bỏ đi một số kí tự và nhầm lẫn thành "bessiexbessieb" - một xâu gồm \(2\) xâu con liên tiếp "bessie" (tên một cô bò mà bác rất yêu quý).

Cho một xâu \(S\) với độ dài tối đa là \(2 \times 10^5\), chỉ chứa các chữ cái in thường, để xoá đi kí tự ở vị trí \(i\) \((1 \le i \le |S|)\) cần mất \(c_i\) đồng. Hãy tìm cách xoá đi sao cho số lượng xâu con liên tiếp "bessie" xuất hiện nhiều nhất, và tính toán chi phí tối thiểu cho cách xoá này.

Input

• Dòng đầu tiên chứa xâu \(S\).
• Dòng thứ hai chứa \(|S|\) số \(c_i\) \((1 \le c_i \le 1000)\).

Ouput

• Dòng đầu tiên chứa số lần xuất hiện nhiều nhất của xâu "bessie".
• Dòng thứ hai chứa chi phí tối thiểu cần trả.

Scoring

• Subtask \(1\): \(|S| \le 2000\).
• Subtask \(2\): \(c_i = 1\) \(\forall i \in [1, |S|]\).
• Subtask \(3\): Không có ràng buộc gì thêm.

besssie
1 1 5 4 6 1 1

1
4

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

1
21

besgiraffesiebessibessie
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

2
7

Vừa hoàn thành xong khoá học về lý thuyết đồ thị, cô bò Bessie đã bắt đầu muốn code một chương trình mô phỏng đồ thị. Hiện tại, do kinh nghiệm còn thiếu, chương trình của cô chỉ có thể mô phỏng được cây có gốc với các node có giá trị khác nhau, đồng thời chương trình mới chỉ có một chức năng duy nhất: ghép cây.

Về cơ bản, ghép cây là chức năng lấy \(2\) node khác nhau có cùng cha trên cây và hợp lại thành \(1\) node duy nhất, giá trị của node mới này là giá trị lớn hơn trong \(2\) giá trị của node cũ, các node con sẽ là hợp các node con của \(2\) node này (nếu có).

Không may là sau khi Bessie thực hiện một số lần ghép cây, chương trình của cô nàng bị văng (crashed), mất đi lịch sử của tất cả các lần ghép mà cô nàng thực hiện. Tất cả những gì Bessie nhớ là cây lúc ban đầu và cây sau khi cô thực hiện các lần ghép.

Bạn được cho \(2\) cái cây này, hãy tìm \(1\) dãy các lần ghép của cô nàng. Dữ liệu đảm bảo dãy này tồn tại.

Input sẽ gồm \(T\) \((1 \le T \le 100)\) bộ test khác nhau. Tổng số node của tất cả các test không quá \(1000\).

Input

• Dòng đầu là số \(T\).
• Dòng thứ hai là số lượng node \(N\) \((2 \le N \le 1000)\) trên cây ban đầu, với các giá trị trên node được đánh số từ \(1\) đến \(N\).
• \(N - 1\) dòng tiếp theo gồm hai số \(v_i\) và \(p_i\) \((1 \le v_i, p_i \le N)\) với ý nghĩa node mang giá trị \(v_i\) là con của node mang giá trị \(p_i\) trong cây ban đầu.
• Dòng tiếp theo là số lượng node \(M\) \((2 \le M \le N)\) của cây sau khi Bessie ghép cây.
• \(M - 1\) dòng tiếp theo gồm hai số \(v_i\) và \(p_i\) \((1 \le v_i, p_i \le N)\) với ý nghĩa node mang giá trị \(v_i\) là con của node mang giá trị \(p_i\) sau khi Bessie ghép cây.

Output

• Với mỗi test, in ra số lần thực hiện ghép cây, theo sau đó là dãy gồm các cặp số \((a_i, b_i)\) là giá trị của \(2\) node được ghép ở lần thứ \(i\), mỗi cặp được in ra trên \(1\) dòng.
• Nếu có nhiều phương án, in ra bất kì.

Scoring

• Subtask \(1\): Số lượng lá (node không có node con) ở cả \(2\) cây là như nhau.
• Subtask \(2\): Không có ràng buộc gì thêm.

1
8
7 5
2 1
4 2
5 1
3 2
8 5
6 2
4
8 5
5 1
6 5

4
2 5
4 8
3 8
7 8