Limak is a little polar bear. Polar bears hate long strings and thus they like to compress them. You should also know that Limak is so young that he knows only first six letters of the English alphabet: 'a', 'b', 'c', 'd', 'e' and 'f'.

You are given a set of q possible operations. Limak can perform them in any order, any operation may be applied any number of times. The i-th operation is described by a string a_{i} of length two and a string b_{i} of length one. No two of q possible operations have the same string a_{i}.

When Limak has a string s he can perform the i-th operation on s if the first two letters of s match a two-letter string a_{i}. Performing the i-th operation removes first two letters of s and inserts there a string b_{i}. See the notes section for further clarification.

You may note that performing an operation decreases the length of a string s exactly by 1. Also, for some sets of operations there may be a string that cannot be compressed any further, because the first two letters don't match any a_{i}.

Limak wants to start with a string of length n and perform n - 1 operations to finally get a one-letter string "a". In how many ways can he choose the starting string to be able to get "a"? Remember that Limak can use only letters he knows.


-----Input-----

The first line contains two integers n and q (2 ≤ n ≤ 6, 1 ≤ q ≤ 36) — the length of the initial string and the number of available operations.

The next q lines describe the possible operations. The i-th of them contains two strings a_{i} and b_{i} (|a_{i}| = 2, |b_{i}| = 1). It's guaranteed that a_{i} ≠ a_{j} for i ≠ j and that all a_{i} and b_{i} consist of only first six lowercase English letters.


-----Output-----

Print the number of strings of length n that Limak will be able to transform to string "a" by applying only operations given in the input.


-----Examples-----
Input
3 5
ab a
cc c
ca a
ee c
ff d

Output
4

Input
2 8
af e
dc d
cc f
bc b
da b
eb a
bb b
ff c

Output
1

Input
6 2
bb a
ba a

Output
0



-----Note-----

In the first sample, we count initial strings of length 3 from which Limak can get a required string "a". There are 4 such strings: "abb", "cab", "cca", "eea". The first one Limak can compress using operation 1 two times (changing "ab" to a single "a"). The first operation would change "abb" to "ab" and the second operation would change "ab" to "a".

Other three strings may be compressed as follows:   "cab" $\rightarrow$ "ab" $\rightarrow$ "a"  "cca" $\rightarrow$ "ca" $\rightarrow$ "a"  "eea" $\rightarrow$ "ca" $\rightarrow$ "a" 

In the second sample, the only correct initial string is "eb" because it can be immediately compressed to "a".

Difficulty: EASY
Tags: Dynamic programming

Graph traversal

Complete search

String algorithms
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
(n, q) = (int(i) for i in input().split(' '))
oper = {}
for i in range(q):
	(key, value) = (i for i in input().split(' '))
	oper[key] = value
abc = ['a', 'b', 'c', 'd', 'e', 'f']
all_v = 0
n -= 2

def generate(mystr, num):
	nonlocal all_v
	try:
		mystr = oper[mystr]
	except KeyError:
		return
	if num == 0:
		if mystr == 'a':
			all_v += 1
		return
	for a in abc:
		generate(mystr + a, num - 1)
for key in oper.keys():
	generate(key, n)
print(all_v)


import collections
import itertools
Operation = collections.namedtuple('Operation', 'from_str to_str')

def is_feasible_operation(base_str, operation):
	return base_str.startswith(operation.from_str)

def conduct_operation(base_str, operation):
	return base_str.replace(operation.from_str, operation.to_str, 1)

def breadth_first_search(init_str, operations):
	q = collections.deque()
	q.append(init_str)
	visited = collections.defaultdict(bool)
	visited[init_str] = True
	while q:
		base_str = q.popleft()
		if base_str == 'a':
			return True
		for operation in operations:
			if not is_feasible_operation(base_str, operation):
				continue
			new_str = conduct_operation(base_str, operation)
			if not visited[new_str]:
				visited[new_str] = True
				q.append(new_str)
	return False

def count_valid_strings(len_str, operations):
	counter = 0
	for chars in itertools.product('abcdef', repeat=len_str):
		init_str = ''.join(chars)
		if breadth_first_search(init_str, operations):
			counter += 1
	return counter

def main():
	(n, q) = list(map(int, input().split()))
	operations = [Operation(*input().split()) for _ in range(q)]
	print(count_valid_strings(n, operations))

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split(' '))
d = {}
(depo, res) = ({}, [])

def bazinga(s):
	if s in depo:
		return depo[s]
	if s[0] not in d:
		depo[s] = 0
	else:
		ans = 0
		for aa in d[s[0]]:
			if len(aa + s[1:]) == n:
				ans += 1
			elif len(aa + s[1:]) > n:
				continue
			else:
				ans += bazinga(aa + s[1:])
		depo[s] = ans
	return depo[s]
for i in range(m):
	(ai, bi) = map(str, input().split(' '))
	if bi in d:
		d[bi] += [ai]
	else:
		d[bi] = [ai]
print(bazinga('a'))


temp = input().split(' ')
(maxLength, initialCount) = [int(x) for x in temp]
dataSet = dict()
for i in range(initialCount):
	temp = input().split(' ')
	(a, b) = [x for x in temp]
	if not b in dataSet.keys():
		dataSet[b] = set()
	dataSet[b].add(a)

def populate(toValue):
	fromValues = set()
	if toValue in dataSet.keys():
		fromValues = dataSet[toValue]
	elif len(toValue) >= 2:
		process = toValue[:1]
		tail = toValue[1:]
		result = populate(process)
		for x in result:
			if x + tail in fromValues:
				continue
			fromValues.add(x + tail)
		dataSet[toValue] = fromValues
	return fromValues
count = 0
currents = ['a']
currentCount = 1
while currentCount < maxLength:
	buffer = []
	for current in currents:
		result = populate(current)
		if len(result) > 0:
			dataSet[current] = result
			buffer = buffer + list(result)
	if len(buffer) > 0:
		currentCount += 1
		currents = buffer
		if currentCount == maxLength:
			count = len(buffer)
	else:
		break
print(count)


from sys import stdin, stdout, setrecursionlimit
import threading

class Tail_Recursion_Optimization:

	def __init__(self, RECURSION_LIMIT, STACK_SIZE):
		setrecursionlimit(RECURSION_LIMIT)
		threading.stack_size(STACK_SIZE)
		return None

class SOLVE:

	def DP(self, s, n, a, b):
		if len(s) == n:
			return 1
		total = 0
		for i in range(len(a)):
			if s[0] == b[i]:
				total += self.DP(a[i] + s[1:], n, a, b)
		return total

	def solve(self):
		R = stdin.readline
		W = stdout.write
		(n, q) = [int(x) for x in R().split()]
		(a, b) = ([None for i in range(q)], [None for i in range(q)])
		for i in range(q):
			(a[i], b[i]) = [x for x in R().split()]
		W('%d\n' % self.DP('a', n, a, b))
		return 0

def main():
	s = SOLVE()
	s.solve()
threading.Thread(target=main).start()


(n, q) = map(int, input().split())
fr = dict()
for i in range(q):
	(a, b) = input().split()
	if b in fr:
		fr[b].append(a)
	else:
		fr[b] = [a]

def dfs(c, cnt):
	nonlocal n
	if cnt == n:
		return 1
	if cnt > n:
		return 0
	nonlocal fr
	if c not in fr:
		return 0
	ans = 0
	for i in fr[c]:
		ans += dfs(i[0], cnt + 1)
	return ans
print(dfs('a', 1))


(n, q) = map(int, input().split())
L = [list(str(input()).split(' ')) for _ in range(q)]
A = [[] for _ in range(6)]
B = 'abcdef'
for i in range(q):
	e = B.index(L[i][1])
	A[e] = A[e] + [L[i][0]]
R = [1, 0, 0, 0, 0, 0]
for i in range(1, n):
	K = [0, 0, 0, 0, 0, 0]
	for j in range(6):
		for k in A[j]:
			e = B.index(k[0])
			K[e] += R[j]
	R = K[:]
print(sum(R))


from collections import defaultdict
(n, q) = map(int, input().split())
ops = {}
for i in range(q):
	(a, b) = input().split()
	ops.setdefault(b, set()).add(a)

def dfs(cur_str, size):
	if size == n:
		return 1
	if size > n:
		return 0
	if cur_str not in ops:
		return 0
	res = 0
	for c in ops[cur_str]:
		res += dfs(c[0], size + 1)
	return res
print(dfs('a', 1))


(n, q) = map(int, input().split())
from collections import defaultdict

def DFS(d, s, t):
	if len(s) == t:
		return 1
	c = 0
	for i in d[s[0]]:
		s1 = i + s[1:]
		c = c + DFS(d, s1, t)
	return c
d = defaultdict(list)
for i in range(q):
	(s1, s2) = input().split()
	d[s2].append(s1)
print(DFS(d, 'a', n))


from functools import reduce
(n, q) = [int(x) for x in input().split()]
substitutions = {}
for _ in range(q):
	(from_str, to_str) = input().split()
	if to_str in substitutions:
		substitutions[to_str].append(from_str)
	else:
		substitutions[to_str] = [from_str]

def generate_str(start_str):
	if len(start_str) == n:
		return 1
	if start_str[0] not in substitutions:
		return 0
	result = 0
	for variant in substitutions[start_str[0]]:
		result += generate_str(variant + start_str[1:])
	return result
print(generate_str('a'))


ans = 0

def check(s, n):
	global ans
	if len(s) == n:
		while len(s) > 1:
			try:
				s = l[s[:2]] + s[2:]
			except KeyError:
				return
		if s == 'a':
			ans += 1
		return
	for i in range(6):
		check(s + chr(97 + i), n)
(n, q) = list(map(int, input().split()))
l = {}
for _ in range(q):
	(s, t) = input().split()
	l[s] = t
check('', n)
print(ans)


(n, k) = map(int, input().split())
l = {}
cnt = 0
for i in range(k):
	(a, b) = input().split()
	l[a] = b
if n == 2:
	print(list(l.values()).count('a'))
	exit(0)

def allcombs(s, prefix, l):
	global cnt
	if l == 0:
		if check(prefix):
			cnt += 1
		return
	for i in s:
		allcombs(s, prefix + i, l - 1)

def check(s):
	while len(s) > 1:
		yes = False
		if s[:2] in l:
			s = l[s[:2]] + s[2:]
			yes = True
		if not yes:
			return False
	if s == 'a':
		return True
	else:
		return False
allcombs(['a', 'b', 'c', 'd', 'e', 'f'], '', n)
print(cnt)


(n, q) = map(int, input().split())
lexicon = {}
for _ in range(q):
	(ai, bi) = input().split()
	if bi in lexicon:
		lexicon[bi].append(ai)
	else:
		lexicon[bi] = [ai]
memo = {}

def solve(s):
	if s in memo:
		return memo[s]
	else:
		count = 0
		if len(s) == n:
			count = 1
		elif s[0] in lexicon:
			for ss in lexicon[s[0]]:
				count += solve(ss + s[1:])
		memo[s] = count
		return count
print(solve('a'))


from collections import defaultdict
from itertools import product

def generate_strings(n):
	for s in product('abcdef', repeat=n):
		yield ''.join(s)

def compress(s, d):
	while len(s) > 1:
		p = s[:2]
		if p not in d:
			break
		s = d[p] + s[2:]
	return s

def solve(n, d):
	return sum((compress(s, d) == 'a' for s in generate_strings(n)))
(n, q) = list(map(int, input().split()))
d = defaultdict(str)
for i in range(q):
	(s1, s2) = input().split()
	d[s1] = s2
print(solve(n, d))


(n, q) = map(int, input().split())
z = {'e': [], 'd': [], 'f': [], 'b': [], 'a': [], 'c': []}
for i in range(q):
	(a, b) = map(str, input().split())
	if b in z:
		z[b].append(a[0])
s = [1, 0, 0, 0, 0, 0]
ind = ['a', 'b', 'c', 'd', 'e', 'f']
for i in range(n - 1):
	a = [0, 0, 0, 0, 0, 0]
	for q in range(6):
		if s[q] != 0:
			for m in z[ind[q]]:
				a[ind.index(m)] += s[q]
	s = a
print(sum(s))


(n, q) = map(int, input().split())
w = []
for _ in range(q):
	w += [input().split()[::-1]]
r = set(['a'])
t = set()
for _ in range(n - 1):
	for s in r:
		for (a, b) in w:
			if s.startswith(a):
				t.add(b + s[1:])
	r = t
	t = set()
print(len(r))


def StringFactory(s):
	temp = []
	for i in range(6):
		run = s[:]
		temp.append(run + [char[i]])
	if len(temp[0]) < n:
		for t in temp:
			StringFactory(t)
	else:
		for v in temp:
			text.append(v)

def opertorFactory(arr):
	global count
	temp = arr[:]
	check = 0
	if len(arr) > 1:
		for c_state in range(q):
			(left, right) = opertor[c_state]
			if left[0] == arr[0] and left[1] == arr[1]:
				temp.pop(0)
				temp.pop(0)
				temp.insert(0, right)
				check = 1
				break
		if check:
			if len(temp) == 1:
				if temp[0] == 'a':
					count += 1
			else:
				opertorFactory(temp)
(n, q) = map(int, input().split())
char = ['a', 'b', 'c', 'd', 'e', 'f']
state = []
opertor = []
text = []
number = [state[:]]
StringFactory(state)
count = 0
for _ in range(q):
	(a, b) = input().split()
	opertor.append([a, b])
for inn in text:
	opertorFactory(inn)
print(count)


alphabet = list('abcdef')

def all_strs_gen(n):
	s = ['a'] * n
	for i in range(0, len(alphabet) ** n):
		yield ''.join(s)
		for j in range(0, n):
			if s[j] == alphabet[-1]:
				s[j] = alphabet[0]
			else:
				s[j] = chr(ord(s[j]) + 1)
				break
(n, q) = [int(x) for x in input().split()]
ops = {}
for i in range(0, q):
	(op, s) = input().split()
	ops[op] = s

def compress(s):
	while s[0:2] in ops:
		s = ops[s[0:2]] + s[2:]
	return s
count = 0
for s in all_strs_gen(n):
	if 'a' == compress(s):
		count += 1
print(count)


def search(rules, m):
	ret = ['a']
	for i in range(m - 1):
		nex = []
		for r in ret:
			(r0, tail) = (r[0], r[1:])
			for (a, b) in rules:
				if a == r0:
					nex.append(b + tail)
		ret = nex
	return len(ret)

def main():
	line = [int(i) for i in input().split()]
	(m, n) = (line[0], line[1])
	rules = []
	for i in range(n):
		line = input().split()
		line.reverse()
		rules.append(line)
	l = search(rules, m)
	print(l)
main()


ans = set()

def gen(cur, n, ops):
	if len(cur) == n:
		ans.add(cur)
	else:
		for t in ops[ord(cur[0]) - ord('a')]:
			gen(t + cur[1:], n, ops)
(n, q) = map(int, input().split())
ops = [[] for i in range(6)]
for i in range(q):
	(s, t) = input().split()
	ops[ord(t[0]) - ord('a')].append(s)
gen('a', n, ops)
print(len(ans))


links = [[], [], [], [], [], []]
(n, q) = map(int, input().split())
for _ in range(q):
	(a, b) = input().split()
	links[ord(b) - ord('a')].append(a[0])

def func(b, depth):
	if depth == n:
		return 1
	count = 0
	for a in links[ord(b) - ord('a')]:
		count += func(a, depth + 1)
	return count
print(func('a', 1))


(n, q) = map(int, input().split())
d = {i: '' for i in 'abcdef'}
for i in range(q):
	(a, b) = input().split()
	d[b] += a[0]
cur = d['a']
ans = len(cur)
for i in range(n - 2):
	nwcur = ''
	for j in cur:
		nwcur += d[j]
	ans = len(nwcur)
	cur = nwcur
print(ans)


import collections
(n, q) = list(map(int, input().split()))
d = collections.defaultdict(list)
(cnt, t) = ([0] * 6, [0] * 6)
for i in range(q):
	(s1, s2) = input().split()
	d[s2].append(s1)
	cnt[ord(s2) - ord('a')] += 1
for s in d['a']:
	t[ord(s[0]) - ord('a')] += 1
for i in range(n - 2):
	p = [0] * 6
	for j in range(6):
		if t[j] == 0:
			continue
		for s in d[chr(j + 97)]:
			p[ord(s[0]) - ord('a')] += t[j]
	t = p
print(sum(t))


(n, q) = map(int, input().split())
go = dict()
for i in range(q):
	(fr, to) = input().split()
	go[fr] = to
ans = 0
for i in range(6 ** n):
	cur = i
	s = ''
	for j in range(n):
		s += chr(ord('a') + cur % 6)
		cur //= 6
	while len(s) > 1:
		fr = s[:2]
		if fr not in go:
			break
		s = go[fr] + s[2:]
	if s == 'a':
		ans += 1
print(ans)


(n, m) = map(int, input().split())
mp = dict()
for _ in range(m):
	(a, b) = input().split()
	mp[a] = b
from itertools import product
count = 0
for t in product('abcdef', repeat=n):
	s = ''.join(t)
	for _ in range(n - 1):
		s = mp.get(s[:2], 'g') + s[2:]
	if s == 'a':
		count += 1
print(count)


(n, m) = list(map(int, input().split()))
d = {}
for i in range(m):
	(t, o) = input().split()
	if o in d:
		d[o].append(t)
	else:
		d[o] = [t]
q = [('a', 0)]
cnt = 0
while q and q[0][1] < n:
	st = q[0]
	q.pop(0)
	if st[1] == n - 1:
		cnt += 1
	if st[0][0] in d:
		for j in d[st[0][0]]:
			q.append((j + st[0][1:], st[1] + 1))
print(cnt)


def main():
	(n, q) = (int(x) for x in input().split())
	L = [None] * q
	for i in range(q):
		(a, b) = (x for x in input().split())
		L[i] = (a, b)
	print(solver(n, L))

def solver(n, L):
	count = 0
	for (a, b) in L:
		if b == 'a':
			count += helper(n - 2, L, a[0])
	return count

def helper(n, L, last):
	if n == 0:
		return 1
	else:
		count = 0
		for (a, b) in L:
			if b == last:
				count += helper(n - 1, L, a[0])
		return count
main()


from collections import defaultdict

def main():
	(n, q) = map(int, input().split())
	instrs = [input().split() for _ in range(q)]
	instr_dict = defaultdict(list)
	for (src, dest) in instrs:
		instr_dict[dest].append(src)
	strs = set()
	last_q = set('a')
	for _ in range(n - 1):
		next_q = set()
		for s in last_q:
			rules = instr_dict[s[0]]
			s = s[1:]
			for rule in rules:
				next_q.add(rule + s)
		last_q = next_q
	print(len(last_q))
main()


import time
pat = {}
(n, q) = (int(i) for i in input().split())
for i in range(q):
	(a, b) = [i for i in input().split()]
	if b in list(pat.keys()):
		pat[b].append(a)
	else:
		pat[b] = [a]
start = time.time()
str = ['a']
for i in range(n - 1):
	newstr = []
	for j in range(len(str)):
		l = str[j][0]
		if l in list(pat.keys()):
			for k in pat[l]:
				newstr.append(k + str[j][1:])
	str = newstr
	if len(str) == 0:
		break
print(len(str))
finish = time.time()


def deep(ch, curn):
	s = 0
	for i in d[ch]:
		if i[0] in 'abcdef' and i[1] in 'abcdef':
			if curn and i[0] in d:
				s += deep(i[0], curn - 1)
			elif curn == 0:
				s += 1
	return s
(n, m) = list(map(int, input().split()))
d = {}
for i in range(m):
	(dec, en) = input().split()
	if en in d:
		d[en].append(dec)
	else:
		d[en] = [dec]
if n == 1:
	print(1)
elif 'a' in d:
	print(deep('a', n - 2))
else:
	print(0)


(a, b) = map(int, input().split())
c = [list(input().split()) for _ in ' ' * b]
z = ['a']
t = []
for i in range(1, a):
	for j in z:
		for k in c:
			if j[0] == k[1]:
				t.append(k[0] + j[1:])
	z = t
	t = []
print(len(z))


from itertools import product
(n, q) = map(int, input().strip().split())
dic = {}
for i in range(q):
	(a, b) = input().strip().split()
	dic[a] = b
count = 0
for i in product('abcdef', repeat=n):
	s = ''.join(i)
	for j in range(n - 1):
		if s[:1] == 'g':
			break
		s = dic.get(s[:2], 'g') + s[2:]
	if s == 'a':
		count += 1
print(count)


def go(i, s):
	global ans
	if i == n:
		if check(s):
			ans += 1
		return
	for c in 'abcdef':
		go(i + 1, s + c)

def check(s):
	if not s in dp:
		dp[s] = 0
		if len(s) > 1:
			for x in ways[s[0:2]]:
				dp[s] = check(x + s[2:len(s)])
	return dp[s]
(n, q) = input().split()
n = int(n)
q = int(q)
ways = {}
for i in 'abcdef':
	for j in 'abcdef':
		ways[i + j] = []
for i in range(q):
	(a, b) = input().split()
	ways[a].append(b)
dp = {}
global ans
ans = 0
dp['a'] = 1
go(0, '')
print(ans)


(n, q) = list(map(int, input().split()))
d = {i: [] for i in 'abcdef'}
for i in range(q):
	(a, b) = list(input().split())
	d[b].append(a[0])
s = d['a']
for i in range(n - 2):
	s0 = s
	s = []
	for i in s0:
		s += d[i]
print(len(s))


import collections
(n, q) = [int(x) for x in input().split()]
g = dict()
for i in range(q):
	(to, f) = input().split()
	if f in g:
		g[f].append(to)
	else:
		g[f] = [to]
counts = dict()

def count(s):
	if s in counts:
		return counts[s]
	if len(s) == n:
		counts[s] = 1
		return 1
	if len(s) > n:
		return 0
	c = s[0]
	cnt = 0
	if not c in g:
		return 0
	suff = s[1:]
	for j in g[c]:
		new_s = j + suff
		cnt += count(new_s)
	counts[s] = cnt
	return cnt
print(count('a'))


import collections
import itertools
GOAL = 'a'
Operation = collections.namedtuple('Operation', 'before after')

def is_possible_operation(original_str, operation):
	return original_str.startswith(operation.before)

def perform_operation(original_str, operation):
	return original_str.replace(operation.before, operation.after, 1)

def judge_dfs(initial_str, operations):
	stack = collections.deque()
	stack.append(initial_str)
	visited = collections.defaultdict(bool)
	visited[initial_str] = True
	while stack:
		original_str = stack.pop()
		if original_str == GOAL:
			return True
		for operation in operations:
			if is_possible_operation(original_str, operation):
				after_str = perform_operation(original_str, operation)
				if not visited[after_str]:
					visited[after_str] = True
					stack.append(after_str)
	else:
		return False

def count_valid_strings(len_init_str, operations):
	cands = itertools.product('abcdef', repeat=len_init_str)
	a = sum((1 for cs in cands if judge_dfs(''.join(cs), operations)))
	return a

def main():
	(n, q) = map(int, input().split())
	operations = [Operation(*input().split()) for _ in range(q)]
	print(count_valid_strings(n, operations))
main()


l = []
(n, q) = map(int, input().split())
al = ['a', 'b', 'c', 'd', 'e', 'f']
qu = []
qu.append(('', 0))
while qu:
	(s, cnt) = qu.pop(0)
	if cnt == n:
		l.append(s)
		continue
	for i in range(6):
		ss = s + al[i]
		qu.append((ss, cnt + 1))
l = list(set(l))
cnt = 0
item = [input().split(' ') for i in range(q)]

def df(s):
	global cnt
	if s == 'a':
		cnt += 1
		return
	elif len(s) == 1:
		return
	for (t1, t2) in item:
		if s[0:2] == t1:
			t = t2 + s[2:]
			df(t)
for s in l:
	df(s)
print(cnt)


(n, q) = map(int, input().split())
d = {}
for _ in range(q):
	x = input()
	(a, b) = (x[0], x[-1])
	if d.get(b) == None:
		d[b] = []
	d[b].append(a)
queue = ['a']
for _ in range(n - 1):
	lst = []
	ex = lst.extend
	for (i, x) in enumerate(queue):
		if d.get(x) != None:
			ex(d[x])
	queue = lst[:]
print(len(queue))


(n, q) = map(int, input().split())
p = {y: [] for y in 'abcdef'}
for i in range(q):
	(x, y) = input().split()
	p[y].append(x[0])
s = p['a']
for j in range(n - 2):
	(t, s) = (s, [])
	for y in t:
		s += p[y]
print(len(s))


from itertools import product
from functools import lru_cache
from string import ascii_lowercase
from sys import stdin, stdout
N = 0
OPS = {}

@lru_cache(maxsize=None)
def backtrack(s):
	if len(s) == 1:
		if s == 'a':
			return True
		return False
	if s[:2] in OPS and backtrack(OPS[s[:2]] + s[2:]):
		return True
	return False

def main():
	(N, q) = [int(x) for x in stdin.readline().rstrip().split()]
	chars = dict(zip(range(6), ascii_lowercase))
	for _ in range(q):
		(l, r) = stdin.readline().rstrip().split()
		OPS[l] = r
	count = 0
	for idx in product(range(0, 6), repeat=N):
		s = ''.join([chars[x] for x in idx])
		count += backtrack(s)
	stdout.write(f'{count}\n')
main()


(n, m) = map(int, input().split())
t = [[] for i in range(6)]
for i in range(m):
	(a, b) = input().split()
	t[ord(b) - ord('a')] += [a]
l = ['a']
A = 0
while len(l) > 0:
	L = []
	for s in l:
		if len(s) == n:
			A += 1
			continue
		for i in range(1):
			ch = s[i]
			for new in t[ord(ch) - ord('a')]:
				L += [s[:i] + new + s[i + 1:]]
	l = set(L)
print(A)


def dfs(s, k):
	global c
	if k == n:
		c += 1
		return
	elif s in adj:
		for u in adj[s]:
			dfs(u[0], k + 1)
	else:
		return
(n, q) = map(int, input().split())
adj = {}
for w in range(q):
	(a, b) = input().split()
	if b not in adj:
		adj[b] = [a]
	else:
		adj[b].append(a)
c = 0
if 'a' in adj:
	dfs('a', 1)
	print(c)
else:
	print(0)


import itertools
from collections import deque

def all_strings(n):
	for i in itertools.product('abcdef', repeat=n):
		yield ''.join(i)
(n, q) = map(int, input().split())
operations = {}
for _ in range(q):
	(a, b) = input().split()
	operations[a] = b
count = 0
for i in all_strings(n):
	while i[:2] in operations:
		x = operations[i[:2]]
		i = x + i[2:]
	if i == 'a':
		count += 1
print(count)


visited = dict()
z = dict()
(n, q) = map(int, input().split())
res = 0

def dfs(s):
	global visited, z, n, res
	visited[s] = 0
	if len(s) == n:
		res += 1
		return
	for (one, two) in z.items():
		if one == s[0]:
			for standin in z[s[0]]:
				if standin + s[1:] not in visited:
					dfs(standin + s[1:])
for i in range(q):
	(x, c) = map(str, input().split())
	if c in z:
		z[c].add(x)
	else:
		z[c] = set()
		z[c].add(x)
dfs('a')
print(res)


from functools import lru_cache
import os
import sys
from io import BytesIO, IOBase

def main():
	zz = ['a', 'b', 'c', 'd', 'e', 'f']
	(n, q) = map(int, input().split())
	d = dict()
	for _ in range(q):
		z = input().split()
		d[z[0]] = z[1]
	ans = 0

	@lru_cache(100)
	def solve(s, i):
		if i == n:
			if s == 'a':
				return 1
			return 0
		ans = 0
		for item in zz:
			z = s + item
			if z in d:
				ans += solve(d[z], i + 1)
		return ans
	for item in zz:
		ans += solve(item, 1)
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(n, q) = map(int, input().split())
queries = {}
for i in range(q):
	(subline, letter) = input().split()
	if letter in queries:
		queries[letter].add(subline)
	else:
		queries[letter] = {subline}
answer = 0
if 'a' in queries:
	lines = ['a']
	curent_length = 1
	while curent_length != n:
		next_lines = sum(([pref + line[1:] for pref in queries[line[0]]] for line in lines if line[0] in queries), [])
		if next_lines:
			lines = next_lines
			curent_length += 1
		else:
			break
	if curent_length == n:
		answer = len(lines)
print(answer)


from collections import defaultdict

def rep(cand, succ):
	ret = set()
	for word in cand:
		for r in succ[word[0]]:
			ret.add(r + word[1:])
	return ret
(n, q) = list(map(int, input().split()))
succ = defaultdict(list)
for _ in range(q):
	(a, b) = input().split()
	succ[b].append(a)
cand = set('a')
for _ in range(n - 1):
	cand = rep(cand, succ)
print(len(cand))


from itertools import product
(n, q) = map(int, input().split())
(T, k) = ({}, 0)
for _ in range(q):
	(a, b) = input().split()
	T[a] = b
for s in product('abcdef', repeat=n):
	s = ''.join(s)
	for _ in range(n - 1):
		a = s[:2]
		if a not in T:
			break
		s = T[a] + s[2:]
	else:
		k += s == 'a'
print(k)


from itertools import product

def bear_and_compressing():
	(n, q) = input().split()
	(n, q) = (int(n), int(q))
	o = []
	j = []
	for _ in range(q):
		o.append(list(input()))
	s = list(product('abcdef', repeat=n))
	for i in s:
		j.append(list(i))
	for _ in range(n):
		for i in j:
			for x in o:
				try:
					if i[0] == x[0] and i[1] == x[1]:
						i.pop(0)
						i[0] = x[3]
				except IndexError:
					continue
	count = j.count(['a'])
	print(count)
bear_and_compressing()


(n, q) = list(map(int, input().split()))
map = {}
for i in range(0, q):
	(two, one) = input().split()
	if one in map:
		map[one].append(two)
	else:
		map[one] = [two]

def sol(map, character, level, n, res):
	if character not in map:
		return res
	if level == n:
		res += len(map[character])
		return res
	for i in range(0, len(map[character])):
		res = sol(map, map[character][i][0], level + 1, n, res)
	return res
res = sol(map, 'a', 2, n, 0)
print(res)


(n, q) = map(int, input().split())
d = {ch: '' for ch in 'abcdef'}
for i in range(q):
	(a, b) = input().split()
	d[b] += a[0]
s = d['a']
for _ in range(n - 2):
	t = ''
	for ch in s:
		t += d[ch]
	s = t
print(len(s))


(n, k) = map(int, input().split())
l = []
for _ in range(k):
	(s1, s2) = input().split()
	l.append((s1, s2))
s = 0

def dfs(last, cl):
	global s, l, n
	if cl == n:
		s += 1
		return
	for item in l:
		if item[1] == last:
			dfs(item[0][0], cl + 1)
dfs('a', 1)
print(s)


def main():
	(n, q) = map(int, input().split())
	(d, nxt, f) = ({c: [] for c in 'abcdef'}, {'a'}, ''.join)
	for _ in range(q):
		(a, b) = input().split()
		d[b].append(a)
	for _ in range(n - 1):
		(cur, nxt) = (nxt, set())
		for l in map(list, cur):
			for s in d[l[0]]:
				l[0] = s
				nxt.add(f(l))
	print(len(nxt))
main()


(n, q) = map(int, input().split())
ops = dict()
for _ in range(q):
	(a, b) = input().split()
	ops[a] = b
from itertools import product
count = 0
for t in product('abcdef', repeat=n):
	s = ''.join(t)
	while len(s) > 1:
		s = ops.get(s[:2], 'g') + s[2:]
	count += s == 'a'
print(count)


(n, q) = map(int, input().split())
operations = [None] * q
for i in range(q):
	operations[i] = input().split()
dp = [0] * 26
dp_buf = [0] * 26
length = 1
dp[0] = 1
cnt = 0
while length < n:
	for (new, c) in operations:
		for i in range(26):
			if dp[i] > 0 and chr(97 + i) == c:
				dp_buf[ord(new[0]) - 97] += dp[i]
	for i in range(26):
		dp[i] = dp_buf[i]
		dp_buf[i] = 0
	s = sum(dp)
	if s == 0:
		cnt = 0
		break
	cnt = s
	length += 1
print(cnt)


p = ['a', 'b', 'c', 'd', 'e', 'f']

def cond(item):
	return item[0] in p and item[1] in p

def dp():
	arr = [[0 for j in range(6)] for i in range(n)]
	for j in range(6):
		arr[0][j] = 1
	for i in range(1, n):
		for j in range(6):
			for item in d:
				if cond(item) and d[item] == j:
					x = ord(item[0]) - ord('a')
					arr[i][j] += arr[i - 1][x]
	return arr[-1][0]
(n, k) = map(int, input().split())
d = {}
for i in range(k):
	(a, b) = input().split()
	d[a] = ord(b) - ord('a')
print(dp())


(n, m) = map(int, input().split())
d = {}
c = {}

def calc(ch, cnt):
	if cnt == n:
		if ch not in d:
			return 0
		return d[ch]
	ans = 0
	if ch not in c:
		return 0
	for i in c[ch]:
		ans += calc(i, cnt + 1)
	return ans
for i in range(0, m):
	(a, b) = input().split()
	if b in d:
		d[b] += 1
	else:
		d[b] = 1
	if b in c:
		c[b].append(a[0])
	else:
		c[b] = [a[0]]
print(calc('a', 2))


(n, q) = map(int, input().split())
d = {}
ch = set()
ans = set()
for i in range(q):
	(a, b) = input().split()
	d.setdefault(b, set()).add(a)
ch = {'a'}
while ch != set():
	b = ch.pop()
	if len(b) == n:
		ans.add(b)
		continue
	for a in d.setdefault(b[0], set()):
		ch.add(''.join((a, b[1:])))
print(len(ans))


from itertools import product as comb
word = 'abcdef'
(n, q) = list(map(int, input().split()))
rep = dict()
for _ in range(q):
	(k, v) = input().split()
	rep[k] = v
ret = set()
for x in comb(word, repeat=n):
	tmp = ''.join(x)
	while len(tmp) > 1:
		before = tmp
		if tmp[:2] not in rep:
			break
		tmp = rep[tmp[:2]] + tmp[2:]
	if tmp == 'a':
		ret.add(x)
print(len(ret))


input1 = input().split()
string_length = int(input1[0])
operations = int(input1[1])
input_val = []
output_val = []
for i1 in range(operations):
	op = input().split()
	input_val.append(op[0])
	output_val.append(op[1])
start_string = ['a']
start_string_new = []
for i1 in range(1, string_length):
	for i2 in range(len(start_string)):
		cur_string = start_string[i2]
		for i3 in range(1):
			cur_let = start_string[i2][i3]
			for i4 in range(len(input_val)):
				if output_val[i4] == cur_let:
					new_string = list(cur_string)
					new_string[i3] = input_val[i4]
					start_string_new.append(''.join(new_string))
	start_string = list(start_string_new)
	start_string_new = []
final_set = list(set(start_string))
print(len(final_set))


from collections import defaultdict
(n, q) = map(int, input().split())
combo = []
for _ in range(q):
	(a, b) = input().split()
	combo.append([b, a])
need = set(['a'])
tmp_next = set()
for ops in range(n - 1):
	for el in need:
		for (a, b) in combo:
			if el.startswith(a):
				tmp_next.add(b + el[1:])
	need = tmp_next
	tmp_next = set()
print(len(need))


import os
import sys
from io import BytesIO, IOBase
from itertools import combinations_with_replacement, permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
s = 'abcdef'
letters = list(s)
(n, m) = list(map(int, input().split()))
mp = {}
for i in range(m):
	(x, red) = list(map(str, input().split()))
	mp[x] = red
combo = list(combinations_with_replacement(letters, n))
perm = []
for i in combo:
	perm += list(permutations(list(i)))
all_words = []
for i in perm:
	x = ''.join((str(x) for x in i))
	all_words.append(x)
unique = set()
for i in all_words:
	flag = 0
	cur = i[0]
	for j in range(1, len(i)):
		two = cur + i[j]
		if two in mp:
			cur = mp[two]
		else:
			flag = 1
			break
	if flag == 0 and cur == 'a':
		unique.add(i)
print(len(unique))


from itertools import permutations, combinations_with_replacement
arr = ['a', 'b', 'c', 'd', 'e', 'f']
(n, q) = list(map(int, input().split()))
y = list(combinations_with_replacement(arr, n))
word = []
total = []
for i in y:
	total += list(permutations(list(i)))
for i in total:
	c = ''
	for j in i:
		c += j
	word.append(c)
d = {}
for i in range(q):
	(k, val) = list(map(str, input().split()))
	d[k] = val
ans = set()
for cur in word:
	f = 0
	temp = cur[0]
	for j in range(1, len(cur)):
		if temp + cur[j] in d:
			temp = d[temp + cur[j]]
		else:
			f = 1
			break
	if f == 0 and temp == 'a':
		ans.add(cur)
print(len(ans))


(n, q) = map(int, input().split())
l = [[] for i in range(6)]
for i in range(q):
	s = input()
	l[ord(s[3]) - ord('a')].append(ord(s[0]) - ord('a'))
ans = 0

def dfs(node, lvl):
	global ans
	if lvl == n - 1:
		ans += 1
		return
	for i in l[node]:
		dfs(i, lvl + 1)
dfs(0, 0)
print(ans)


def dfs(w, l, n, m):
	if l == n:
		return 1
	t = w[0]
	if t not in m:
		return 0
	c = 0
	for f in m[t]:
		nw = f + w[1:]
		c += dfs(nw, l + 1, n, m)
	return c

def main():
	(n, q) = map(int, input().split())
	m = dict()
	for i in range(q):
		(f, t) = input().split()
		if t not in m:
			m[t] = [f]
		else:
			m[t].append(f)
	ans = dfs('a', 1, n, m)
	print(ans)
main()


from collections import defaultdict
(n, q) = map(int, input().split())
es = defaultdict(list)
for _ in range(q):
	(a, b) = input().split()
	es[b].append(a)
ss = set('a')
for i in range(1, n):
	ssp = set()
	for s in ss:
		for e in es[s[0]]:
			ssp.add(e + s[1:])
	ss = ssp
	if not ss:
		break
print(len(ss))


read = lambda : map(int, input().split())
(n, q) = read()
s = [tuple(input().split()) for i in range(q)]
dp = [[0] * (n + 1) for i in range(6)]
alp = 'abcdef'
for c in alp:
	res = 0
	for (a, b) in s:
		if b == c:
			res += 1
	dp[ord(c) - ord('a')][0] = res
for j in range(1, n - 1):
	for c in alp:
		res = 0
		for (a, b) in s:
			if b == c:
				res += dp[ord(a[0]) - ord('a')][j - 1]
		dp[ord(c) - ord('a')][j] = res
ans = dp[0][n - 2]
print(ans)


(n, q) = list(map(int, input().split()))
ql = [input().split() for _ in range(q)]
d = {c: [q[0] for q in ql if q[1] == c] for c in 'abcdef'}
cl = ['a']
for i in range(n - 1):
	cl = [cc[0] for c in cl for cc in d[c]]
print(len(cl))


from collections import defaultdict
(n, k) = map(int, input().split())
typ = defaultdict(lambda : [])
for _ in range(k):
	(x, y) = input().split()
	typ[y].append(x[0])
curr = 2
val = typ['a']
while curr < n:
	temp = []
	for i in val:
		for j in typ[i]:
			temp.append(j)
	val = temp
	curr += 1
print(len(val))


(n, q) = map(int, input().split())
mass = []
count = 0
for i in range(q):
	mass.append(tuple(input().split()))

def transform(string):
	tmp_mass = []
	for i in range(q):
		if mass[i][1] == string[len(string) - 1]:
			tmp_mass.append(mass[i][0])
	return tmp_mass
strings = ['a']
for i in range(n - 1):
	tmp_mass2 = []
	for elem in strings:
		lists_from_letter = transform(elem[0])
		tmp_mass2 += lists_from_letter
	strings = tmp_mass2
print(len(strings))