Gravity Guy

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef likes to play games a lot. Gravity Guy is one such interesting game.
"Gravity Guy is an arcade sidescrolling game in which the player controls Gravity Guy by tapping the screen to switch gravity. The objective in this game is to run as far as possible while avoiding being trapped by obstacles, falling, or flying off the screen. If hit by obstacles, the game is over."
Chef is so addicted to this game that each night he dreams of himself being in the game as Gravity Guy. He has two lanes in front of him represented by two strings of equal length named as L_{1} and L_{2}. Each of the two lanes consists of some clean blocks represented by '.' and some dirty blocks represented by '#'.
Chef can start running from the beginning of any of the two lanes and cannot step over any dirty block ( '#' ) encountered during his journey. He has to complete his journey by reaching the end block of any of the two lanes.
Chef can use the following jumps to reach his destination. Considering chef is at x^{th} block of some lane.
 He can jump to x+1^{th} block of the same lane.
 He can switch gravity quickly and jump to x^{th} block of the other lane.
 He can switch gravity and jump to x+1^{th} block of the other lane.
You have to tell him whether he can reach his destination or not. If it is possible for him to reach his destination, then Chef is interested in knowing the minimum number of gravity switches required to reach the destination.
Input
First line of input contains a single integer T denoting the number of test cases. Each test case consists of 2 lines. First line of each test case contains a string denoting lane L_{1}. Second line of each test case contains a string denoting lane L_{2}.
Output
For each test case, print "Yes" (without quotes) in the first line if Chef is able to reach the destination followed by a line containing an integer denoting minimum number of gravity switches required to reach to the destination. Print a single line containing the word "No" (without quotes) otherwise.
Constraints
 1 ≤ T ≤ 10^{5}
 1 ≤ L_{1} ≤ 2 × 10^{5}, where S denotes the length of string S
 L_{1} = L_{2}
Subtasks
Subtask 1 (25 points)
 Sum of L_{1} over all test cases in one file it at most 200.
 Only "Yes"/"No" response will be evaluated.
Subtask 2 (25 points)
 Sum of L_{1} over all test cases in one file it at most 200.
Subtask 3 (25 points)
 Sum of L_{1} over all test cases in one file it at most 10^{6}.
 Only "Yes"/"No" response will be evaluated.
Subtask 4 (25 points)
 Sum of L_{1} over all test cases in one file it at most 10^{6}.
Example
Input: 3 #...# .###. #.#.#. .#.#.# #... #... Output: Yes 2 Yes 5 No
Explanation
 Test 1: Chef will start his journey from L_{2}, switch from L_{2} to L_{1} and finally land up at last block of L_{2} by switching from L_{1} to L_{2}. Therefore, he requires total 2 gravity switches to reach the destination.
 Test 3: Chef cannot start his journey as starting block of both the lanes L_{1} & L_{2} are dirty and he cannot step over them.
In Subtask 1 and Subtask 3, only "Yes"/"No" response will be evaluated. Thus, for example, the output
Yes 1 Yes 8 No
is considered as a correct output for the example input.
Author:  ma5termind 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/GRGUY 
Tags  aug15, dynamicprogramming, greedy, ma5termind, simple 
Date Added:  1042015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 