Contest giao lưu lớp 10 các trường Chuyên (Lần 4)

Trong phòng thí nghiệm nano, các nhà khoa học đang nghiên cứu một quy trình tổng hợp vật chất mang tên "nhân hai cộng một". Quy trình này biến đổi một cấu trúc vật chất (được mô tả bằng một xâu ký tự \(a\)) theo nguyên tắc sau:

1. Nhân đôi: Tạo ra một bản sao của xâu \(a\) và gắn vào ngay sau xâu gốc (thu được \(a + a\)).
2. Cộng một: Gắn thêm một nguyên tử mới (là một ký tự \(c\) bất kỳ trong bảng chữ cái) vào cuối xâu vừa tạo.

Ví dụ: Từ xâu ab, quy trình sẽ tạo ra ab + ab + x = ababx.

Mọi cấu trúc đều bắt đầu từ "hư không" (xâu rỗng). Nhà nghiên cứu An vừa tìm thấy một số mẫu vật lạ và muốn kiểm tra nguồn gốc của chúng. Với mỗi mẫu vật (xâu \(s\)), An có hai loại câu hỏi:

• Loại 1: Xâu \(s\) này có phải là kết quả thuần túy của quy trình trên (xuất phát từ xâu rỗng) hay không?
• Loại 2: Nếu ta được phép sắp xếp lại vị trí các nguyên tử trong \(s\) tùy ý, liệu có thể tạo ra một cấu trúc đúng chuẩn quy trình trên (có thể được tạo từ xâu rỗng) hay không?

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(1 \le T \le 10\)) là số lượng mẫu vật cần kiểm tra.
• \(T\) dòng tiếp theo, mỗi dòng chứa thông tin về một mẫu vật gồm:
  • Một xâu ký tự \(s\) chỉ gồm các chữ cái in thường (độ dài không quá \(270\,000\) ký tự).
  • Một số nguyên \(\theta \in \{1, 2\}\) biểu thị loại câu hỏi (\(\theta = 1\) là hỏi Loại 1, \(\theta = 2\) là hỏi Loại 2).

Output

• Với mỗi mẫu vật, in ra YES nếu câu trả lời là có thể, hoặc NO nếu không thể.

Example

4
a 1
aab 1
aba 1
aba 2

YES
YES
NO
YES

Subtask

• Subtask 1: \(30\%\) số điểm có độ dài xâu \(s \le 3\) và \(\theta = 1\).
• Subtask 2: \(20\%\) số điểm khác có \(\theta = 1\).
• Subtask 3: \(30\%\) số điểm khác có độ dài xâu \(s \le 3\).
• Subtask 4: \(20\%\) số điểm còn lại không có giới hạn gì thêm.

Tại trung tâm nghiên cứu AI, có hai robot thám hiểm Alpha và Beta đang cần nạp năng lượng. Hệ thống sạc bao gồm các trạm năng lượng nằm trên một trục thẳng, tổng cộng có \(2 \times n\) trạm sạc. Mỗi trạm sạc cung cấp một loại năng lượng thuộc cấp độ từ \(1\) đến \(n\).

Để kích hoạt hệ thống tối thượng, cả Alpha và Beta đều phải lần lượt thu thập đủ bộ năng lượng từ cấp \(1\) đến cấp \(n\) theo đúng thứ tự (tức là phải có cấp \(i - 1\) mới được nạp cấp \(i\)).

Hệ thống vận hành theo quy tắc như sau:

• Ban đầu, hệ thống sẽ đưa hai robot đến vị trí của trạm năng lượng cấp \(1\) gần nhất (chi phí di chuyển ban đầu này được coi là \(0\) hoặc đã được tính toán trong khâu chuẩn bị, không tính vào kết quả).
• Mỗi trạm sạc chỉ phục vụ được cho một robot duy nhất.
• Khoảng cách giữa hai trạm liền kề là \(1\) đơn vị.
• Mục tiêu là điều khiển hai robot di chuyển từ các trạm cấp \(i\) sang các trạm cấp \(i + 1\) sao cho tổng quãng đường cả hai đi được là nhỏ nhất.

Hệ thống đôi khi gặp sự cố và đảo vị trí các trạm sạc cho nhau. Với mỗi thay đổi đó, bạn hãy tính toán lại tổng quãng đường tối ưu.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n, q\) (\(1 \le n, q \le 2 \cdot 10^5\)).
• Dòng tiếp theo gồm \(2 \times n\) số nguyên dương \(a_1, a_2, \dots, a_{2n}\) (\(1 \le a_i \le n\)) là cấp độ năng lượng tại các trạm. Dữ liệu đảm bảo mỗi cấp độ xuất hiện đúng 2 lần.
• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(i, j\) (\(1 \le i < j \le 2n\)) mô tả sự cố hoán đổi trạm sạc ở vị trí \(i\) và \(j\).

Output

• Với mỗi truy vấn hoán đổi, in ra tổng quãng đường nhỏ nhất tìm được.

Example

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

7
12

Scoring

• Subtask 1 (\(20\%\) số điểm): \(n, q \le 6\).
• Subtask 2 (\(20\%\) số điểm): \(n, q \le 16\).
• Subtask 3 (\(20\%\) số điểm): \(n, q \le 200\).
• Subtask 4 (\(20\%\) số điểm): \(n, q \le 2000\).
• Subtask 5 (\(20\%\) số điểm): không có giới hạn gì thêm.

Thành phố nơi G ở có \(n\) địa điểm du lịch nổi tiếng và \(m\) con đường một chiều nối các điểm du lịch này. Con đường thứ \(i\) đi từ điểm du lịch \(u_i\) đến điểm du lịch \(v_i\).

Hiện tại, hệ thống giao thông đảm bảo rằng với mọi cặp điểm du lịch \(x, y\), luôn tồn tại một đường đi (có thể đi theo chiều mũi tên hoặc ngược chiều mũi tên) giữa chúng.

Mùa lễ hội sắp đến, thành phố muốn quy hoạch lại và chọn ra đúng \(n - 1\) trong số \(m\) con đường hiện có để xây dựng lại. Các con đường được chọn phải thỏa mãn tính chất sau:

• Có đúng \(1\) điểm du lịch không có con đường nào (trong số các đường được chọn) đi đến nó. Điểm này sẽ đóng vai trò là nơi bắt đầu tham quan.
• Tất cả các điểm du lịch còn lại, mỗi điểm có chính xác một con đường (trong số các đường được chọn) đi đến nó.

Hội đồng thành phố nhờ bạn kiểm tra xem có phương án nào thỏa mãn hay không. Nếu có, hãy chỉ ra một phương án cụ thể.

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(1 \le T \le 3\)) là số bộ dữ liệu cần giải quyết.
• \(T\) nhóm dòng tiếp theo mô tả các bộ dữ liệu, mỗi nhóm có định dạng:
  • Dòng đầu tiên gồm hai số nguyên dương \(n, m\) (\(1 \le n \le 10^5\); \(n - 1 \le m \le 1.5 \cdot 10^5\)).
  • \(m\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(u_i, v_i\) (\(1 \le u_i, v_i \le n\); \(u_i \neq v_i\)) mô tả con đường thứ \(i\).

Output

• Với mỗi bộ dữ liệu, nếu không tìm được phương án thỏa mãn, in ra NO.
• Ngược lại, in ra YES trên dòng đầu tiên. Dòng tiếp theo in ra một xâu nhị phân độ dài \(m\):
  • Ký tự thứ \(i\) là 0: Con đường thứ \(i\) không được chọn.
  • Ký tự thứ \(i\) là 1: Con đường thứ \(i\) được chọn.
• Nếu có nhiều phương án, in ra một phương án bất kỳ.

Example

1
4 4
2 1
2 3
4 2
4 3

YES
1011

Scoring

• Subtask \(1\) (\(8\%\) số điểm): \(n = m \le 2000\).
• Subtask \(2\) (\(12\%\) số điểm): \(m \le 20\).
• Subtask \(3\) (\(12\%\) số điểm): \(n \le 20\).
• Subtask \(4\) (\(16\%\) số điểm): \(n \le 2000, m \le 4000\).
• Subtask \(5\) (\(24\%\) số điểm): \(u_i < v_i\) với mọi \(i\).
• Subtask \(6\) (\(28\%\) số điểm): không có ràng buộc gì thêm.