Problem Statement

Markov takes out his Snakes and Ladders game and stares at the board, and wonders: If he had absolute control on the die, and could get it to generate any number (in the range 1-6) he desired, what would be the least number of rolls of the die in which he'd be able to reach the destination square (Square Number 100) after having started at the base square (Square Number 1)?

Rules

1. Markov has total control over the die and the face which shows up every time he tosses it. You need to help him figure out the minimum number of moves in which he can reach the target square (100) after starting at the base (Square 1).
2. A die roll which would cause the player to land up at a square greater than 100, goes wasted, and the player remains at his original square. Such as a case when the player is at Square Number 99, rolls the die, and ends up with a 5.
3. If a person reaches a square which is the base of a ladder, (s)he has to climb up that ladder, and he cannot come down on it. If a person reaches a square which has the mouth of the snake, (s)he has to go down the snake and come out through the tail - there is no way to climb down a ladder or to go up through a snake.

Input Format

The first line contains the number of tests, T. T testcases follow.

For each testcase, there are 3 lines.

The first line contains the number of ladders and snakes, separated by a comma.
The second is a list of comma separated pairs indicating the starting and ending squares of the ladders. The first point is the square from which a player can ascend and the second point is his final position.
The third is a list of comma separated pairs indicating the starting and ending (mouth and tail) squares of the snakes. the first point is the position of the mouth of the snake and the second one is the tail.
Multiple comma separated pairs of snakes and ladders are separated by a single space.

Constraints
The board is always of the size 10 x 10
1 <= T <= 10
1 <= Number of Snakes <= 15
1 <= Number of Ladders <= 15
Squares are always numbered 1 to 100 and the order can be seen in the image above.

Output Format

For each of the T test cases, output one integer each on a new line, which is the least number of moves (or rolls of the die) in which the player can reach the target square (Square Number 100) after starting at the base (Square Number 1). This corresponds to the ideal sequence of faces which show up when the die is rolled.

Sample Input

3
3,7
32,62 42,68 12,98
95,13 97,25 93,37 79,27 75,19 49,47 67,17
5,8
32,62 44,66 22,58 34,60 2,90
85,7 63,31 87,13 75,11 89,33 57,5 71,15 55,25
4,9
8,52 6,80 26,42 2,72
51,19 39,11 37,29 81,3 59,5 79,23 53,7 43,33 77,21

Sample Output

3
3
5

############################# editorial#######################################

  we need to apply dfs starting from the cell no 1.. treat entire 2d array as a single 1d array (ie 1d array of size 100 ).. now from each position we can move to either i+1,i+2... i+6 th position..    if there is no snack or ladder at position i+1,i+2.. then simply push that block in stack with level+1(if i+k th (k=1 to 6)block have not visited with level <current level +1 ).(where level is the  step to rach ith block ). else if there is a ladder in the i+k (k=1 to 6)block then we have to push that new block which is connected  with the ladder at other end with level+1.. finally if i+k(k=1 to 6) th block contain snack then we have to go lower but if we have already covered that node (tail end of snack ) whit level <current level+1  then do not push than node in the stack.. for checking that keep a maxlev[i] array which contain best soln to reach ith block. ...

##################################code#########################################

include<iostream>
using namespace std;
#include<bits/stdc++.h>
#include<stack>
int hs[1001];/// contain hashing of snack present at index i of not
int hl[1001];//  contain hashing of  ladders  present at index i of not

int vm[1001];// contain min step required to reach ith block;
int main()
 {
     
  //freopen("abc.txt","r",stdin);
  
  int t;
    cin>>t;
 
     while(t--)
      {
       
        for(int i=0;i<102;i++)// reset hash
         {
          hs[i]=0;
          hl[i]=0;
         }
       char cc;
        int l,s;
         cin>>l>>cc>>s;
          for(int i=0;i<l;i++)
           {
            int st,en;
            char  c;
            cin>>st>>c>>en;
              hl[st]=en;//  hashing ladder 
           }
         for(int i=0;i<s;i++)
          {
             int st,en;
            char  c;
            cin>>st>>c>>en;
            hs[st]=en;//hashing snack
          }
           for(int i=0;i<110;i++)  vm[i]=INT_MAX;//mak max step initi
          
   stack<pair<int,int> > sta; contain node no and no of step to reach there
        sta.push(make_pair(1,0)); //push start at lev=1
          vm[1]=0;
          int ans=INT_MAX;
          while(!sta.empty())
           {
            int current=sta.top().first;
            int lev=sta.top().second;
            sta.pop();
             
            
              for(int i=1;i<=6;i++)
               {
                if(current+i==100   && ans>lev+1)  // if reach at 100 block with less step
                {
                 ans=lev+1;
                 
                 break;
                }
                else if(current+i>=100) 
                {
                 break;
                }

                   // if no snack and ladder then 
               else if(hs[current+i]==0  && hl[current+i]==0  && vm[current+i]>lev+1)// if this new  node is not visited earlier with less staps then only push it 
                {
                 sta.push(make_pair(current+i,lev+1));
                 vm[current+i]=lev+1;
                }
                  // if there is a snack in the current+i th block

                else if(hs[current+i]!=0  && vm[hs[current+i]]>lev+1)// if this new  node is not visited earlier with less staps then only push it 

                 {
                  //cout<<"pussing back "<<endl;
                  sta.push(make_pair(hs[current+i],lev+1));
                  vm[hs[current+i]]=lev+1;
                 }

// if there is a ladder in the current +i block 
                 else if( hl[current+i]!=0  &&  vm[hl[current+i]]>lev+1)
                  {
                   sta.push(make_pair(hl[current+i],lev+1));
                   vm[hl[current+i]]=lev+1;
                  }
                   
               }
            
           }
          cout<<ans<<endl;
      }
      
      return 0;
    
 }