Button Pressing
Time limit2sMemory limit1024 MB
Given initial lamp states A and target states B, decide whether pressing buttons that flip neighboring lamps (only when the button's own lamp is on) can reach B.
- Level
Medium5 of 10
- Topics
- String, Greedy, Simulation
- Solved
- No attempts yet
Problem
You are given buttons (numbered from to ) and lamps (numbered from to ). Each lamp can be either on or off. Initially, lamp is on if , and off if .
Button is connected to lamp (if ) and lamp (if ). In one move, you can press button only if lamp is on. When a button is pressed, the state of the lamps connected to it is toggled: a lamp that was off turns on, and a lamp that was on turns off. Button is not connected to lamp , so pressing button does not change the state of lamp .
After zero or more moves, you want lamp to be on if , and off if . Determine whether this is possible.
Input
The first line contains an integer (), the number of test cases. Each test case consists of three lines.
The first line of each test case contains an integer (). The sum of over all test cases does not exceed 200000.
The second line contains a string of length . Each character is 0 or 1. The -th character is the initial state of lamp .
The third line contains a string of length . Each character is 0 or 1. The -th character is the desired final state of lamp .
Output
For each test case, print YES on a single line if all lamps can be brought to their desired states, or NO otherwise.