Button Pressing

시간 제한2초메모리 제한1024 MB

요약
초기 상태 A가 주어질 때 램프 i가 켜져 있을 때만 버튼 i를 눌러 램프 i-1과 i+1을 토글할 수 있다. 목표 상태 B에 도달할 수 있는지 판정한다.
난이도

보통10점 중 7점

유형
그리디, 구현, 완전 탐색, 시뮬레이션
정답자
아직 제출이 없습니다

문제

You are given NN buttons (numbered from 11 to NN) and NN lamps (numbered from 11 to NN). Each lamp can either be on or off. Initially, lamp ii is on if A_i=1A\_i = 1, and off if A_i=0A\_i = 0.

Button ii is connected to lamp i−1i - 1 (if i>1i > 1) and lamp i+1i + 1 (if i<Ni < N). In one move, you can press a button ii only if lamp ii is on. When a button is pressed, the state of the lamps connected to this button is toggled. Formally, the lamps will be on if it was off previously, and the lamps will be off if it was on previously. Note that lamp i is not connected to button ii, thus, the state of lamp ii does not change if button ii is pressed.

After zero or more moves, you want lamp ii to be on if B_i=1B\_i = 1, and off if B_i=0B\_i = 0. Determine if it is possible to achieve this task.

입력

This problem has multiple test cases. The first line consists of an integer TT (1≤T≤10001 ≤ T ≤ 1000), which represents the number of test cases. Each test case consists of three lines.

The first line of each test case consists of an integer NN (3≤N≤200,0003 ≤ N ≤ 200\\, 000). The sum of NN over all test cases does not exceed 200,000200\\, 000.

The second line of each test case consists of a string AA of length NN. Each character of AA can either be 00 or 11. The iith character represents the initial state of lamp ii.

The third line of each test case consists of a string AA of length NN. Each character of BB can either be 00 or 11. The iith character represents the desired final state of lamp ii.

출력

For each test case, output YES in a single line if the final state of all lamps can be reached after zero or more moves, or NO otherwise.

예제2

  1. 예제 1

    입력
    2
    4
    0101
    0100
    3
    000
    010
    
    예상 출력
    YES
    NO
    
  2. 예제 2

    입력
    5
    7
    0101011
    1111010
    5
    11111
    00000
    4
    1101
    1101
    6
    101010
    100100
    3
    000
    000
    
    예상 출력
    NO
    NO
    YES
    YES
    YES