Biến u thành v được hay không ?

Xem PDF



Tác giả:
Dạng bài
Điểm: 320 Thời gian: 1.0s Bộ nhớ: 98M Input: bàn phím Output: màn hình

Cho hai xâu nhị phân \(u\)\(v\) và một phép toán sau:

  • Chọn hai phần tử kề nhau bất kỳ của xâu \(u\). Giả sử đó là \(p\)\(q\).

  • Đặt \(x = p \oplus q\)\(y = p | q\), sau đó thay thế hai phần tử \(p,q\) thành \(x,y\) theo thứ tự tuỳ ý. Tức là \((p,q)\) có thể thay thế thành \((x,y)\) hoặc \((y,x)\)

Hỏi ta có thể biến xâu \(u\) thành xâu \(v\) hay không nếu ta thực hiện phép toán trên với số lần tuỳ ý ?

Ghi chú: \(\oplus\) - Là phép toán XOR và \(|\) - Là phép toán OR

Input

  • Dòng thứ nhất chứa số \(t(1\le t\le 100)\) - Thể hiện số testcase

  • \(t\) block tiếp theo, mỗi block gồm 2 dòng chứ hai xâu \(u,v(1\le |u|,|v|\le 10^4)\). Biết rằng độ dài hai xâu \(u,v\) không nhất thiết bằng nhau.

Output

  • Ứng với mỗi testcase, in ra "YES" nếu xâu \(u\) có thể thành xâu \(v\), ngược lại in ra "NO"

Example

Test 1

Input
2
10
111
111
110
Output
NO
YES

Bình luận