Untitled

import time
import sys

#test_string = "2 3\nabcdx\ndabca\nabcd dabc\ndabc abcd\nabcd dabc"
#test_string2 = "10 10\nabbcc\ncaabb\nbacab\ncbbcb\ncbcba\nbaccc\nccaba\ncbcca\naaacb\nbccba"
#test_string3 = "5 3\nthere\nwhere\ninput\nputin\nhello\nthere where\nputin input\nhello putin"


N, Q = sys.stdin.readline().split()
Data = ""
for i in range(0, int(N) + int(Q)):
    Data = Data + input() + "\n"

Data = N + "\n" + Q + "\n" + Data
#print(Data)

def get(word, node_list):
    counter = 0
    for i in range(0, len(node_list)):
        counter += 1
        if(word == node_list[i]):
            return i
    return -1

def letter_to_int(string):
    return ord(string) - 97

def format(string):
    array = string.split()
    nodes = int(array.pop(0))
    pairs = int(array.pop(0))
    
    node_list = array[0: nodes]
    pair_list = array[nodes: len(array)]

    for i in range(0, len(pair_list)):
        pair_list[i] = get(pair_list[i], node_list)

    matrix = []
    #O(N)
    for i in range(0, nodes):
        nei = []
        #O(N)
        for j in range(0, nodes):
            #O(1)
            if a_isneito_b(node_list[j], node_list[i]):
                nei.append(j)
        matrix.append(nei)
    #print(matrix)
    return[pair_list, matrix]
    
#O(1)
def a_isneito_b(A, B):
    
    #O(1)
    count_list_A = [0] * 28
    count_list_B = [0] * 28
    
    #O(len(A)) = O(5) = O(1)
    for i in range(0, len(A)):
        count_list_A[letter_to_int(A[i])] += 1
    
    #O(len(B)) = O(5) = O(1)
    for i in range(1, len(B)):
        count_list_B[letter_to_int(B[i])] += 1

    #O(28) = O(1)
    for i in range(0, 28):
        if(count_list_A[i] < count_list_B[i]):
            return False
    return True

#accepts the matrix(neigbour) that format returns
def algorithm(neighbor, s, t):
    if(s == t):
        print(0)
        return
    
    nbr_nodes = len(neighbor)
    pred_list = [-1] * nbr_nodes
    
    visited = [False] * nbr_nodes
    visited[s] = True
    q = [s]

    k = 0
    while not k == len(q):
        v = q[k]
        k = k + 1

        for w in neighbor[v]:
            
            if not visited[w]:
                visited[w] = True
                q.append(w)
                pred_list[w] = v
                
                if w == t:
                    counter = 0
                    current = w
                    
                    #denna while loop kör inte en gång för varje w
                    #utan endast en gång då w == t
                    #loopen har maximal längd N
                    #och är därmed O(N)
                    #den totala komplexiteten som denna loop
                    #adderar till algoritmen är alltså O(N)
                    #vilket är acceptabelt
                    
                    while(pred_list[current] != -1):
                        current = pred_list[current]
                        counter += 1
                    
                    #print("path found")
                    print(counter)
                    
                    return
    
    print("Impossible")






#data = format(test_string2)
#matrix = data[2]
#start = time.time()
#algorithm(matrix, 1, 2)
#end = time.time()
#print(end - start)

#data = format(test_string3)
#pair_list = data[1]
#matrix = data[2]

#for i in range(0, len(pair_list), 2):
    #algorithm(matrix, i, i + 1)


start1 = time.time()
data = format(Data)
end1 = time.time()
pair_list = data[0]
matrix = data[1]

start2 = time.time()
for i in range(0, len(pair_list), 2):
    algorithm(matrix, pair_list[i], pair_list[i + 1])
end2 = time.time()

print(end1 - start1)
print(end2 - start2)