만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

버튼 누르기

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

요약
초기 램프 상태 A와 목표 상태 B가 주어질 때, 램프 i가 켜져 있을 때만 누를 수 있고 램프 i-1과 i+1의 상태를 바꾸는 버튼으로 B에 도달할 수 있는지 판별합니다.
난이도

보통10점 중 5점

유형
문자열, 그리디, 시뮬레이션
정답자
아직 제출이 없습니다

문제

NN개의 버튼(1번부터 NN번까지)과 NN개의 전구(1번부터 NN번까지)가 있다. 각 전구는 켜져 있거나 꺼져 있다. 처음에 Ai=1A_i = 1이면 전구 ii는 켜져 있고, Ai=0A_i = 0이면 꺼져 있다.

버튼 ii는 전구 i−1i - 1(단, i>1i > 1인 경우)과 전구 i+1i + 1(단, i<Ni < N인 경우)에 연결되어 있다. 한 번의 동작에서 전구 ii가 켜져 있을 때에만 버튼 ii를 누를 수 있다. 버튼을 누르면 연결된 전구의 상태가 반전된다. 꺼져 있던 전구는 켜지고, 켜져 있던 전구는 꺼진다. 버튼 ii는 전구 ii와 연결되어 있지 않으므로, 버튼 ii를 눌러도 전구 ii의 상태는 바뀌지 않는다.

0번 이상의 동작 후에 Bi=1B_i = 1이면 전구 ii가 켜져 있고, Bi=0B_i = 0이면 꺼져 있도록 만들 수 있는지 판단하라.

입력

첫 줄에 테스트 케이스의 개수 TT (1≤T≤10001 \le T \le 1000)가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다.

각 테스트 케이스의 첫 줄에는 정수 NN (3≤N≤2000003 \le N \le 200000)이 주어진다. 모든 테스트 케이스의 NN 합은 200000을 넘지 않는다.

둘째 줄에는 길이 NN의 문자열 AA가 주어진다. 각 문자는 0 또는 1이다. ii번째 문자는 전구 ii의 초기 상태이다.

셋째 줄에는 길이 NN의 문자열 BB가 주어진다. 각 문자는 0 또는 1이다. ii번째 문자는 전구 ii의 목표 상태이다.

출력

각 테스트 케이스마다 모든 전구를 목표 상태로 만들 수 있으면 YES를, 그렇지 않으면 NO를 한 줄에 출력한다.

예제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