Given an array of lowercase strings A[] of size N, determine if the strings can be chained together to form a circle.
A string X can be chained together with another string Y if the last character of X is same as first character of Y. If every string of the array can be chained with exactly two strings of the array(one with the first character and second with the last character of the string), it will form a circle.
For example, for the array arr[] = {"for", "geek", "rig", "kaf"} the answer will be Yes as the given strings can be chained as "for", "rig", "geek" and "kaf"
Example 1:
Input:
N = 3
A[] = { "abc", "bcd", "cdf" }
Output:
0
Explaination:
These strings can't form a circle 
because no string has 'd'at the starting index.
Example 2:
Input:
N = 4
A[] = { "ab" , "bc", "cd", "da" }
Output:
1
Explaination:
These strings can form a circle 
of strings.
Your Task:
You don't need to read input or print output. Your task is to complete the function isCircle() which takes the length of the array N and the array A as input parameters and returns 1 if we can form a circle or 0 if we cannot.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints: 
1 ≤ N ≤ 10^{4}
1 ≤ Length of strings ≤ 20

Difficulty: MEDIUM
Tags: String algorithms

Graph algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



class Solution:

    def isCircle(self, N, A):

        # code here

Solutions:
def dfs(node, adj, vis):
	vis[node] = 1
	for i in adj[node]:
		if not vis[i]:
			dfs(i, adj, vis)

def detectCycle(src, adj, mark):
	vis = [0] * 26
	dfs(src, adj, vis)
	for i in range(26):
		if not vis[i] and mark[i] == 1:
			return 0
	return 1

class Solution:

	def isCircle(self, N, A):
		mark = [0] * 26
		adj = [[] for _ in range(26)]
		in_degree = [0] * 26
		out_degree = [0] * 26
		for i in A:
			u = ord(i[0]) - ord('a')
			v = ord(i[-1]) - ord('a')
			adj[u].append(v)
			mark[u] = mark[v] = 1
			in_degree[v] += 1
			out_degree[u] += 1
		for i in range(26):
			if in_degree[i] != out_degree[i]:
				return 0
		return detectCycle(ord(A[0][0]) - ord('a'), adj, mark)


from collections import defaultdict

class Solution:

	def isCircle(self, N, A):
		(d, d1, v, c) = (defaultdict(list), defaultdict(int), set(), 0)
		for i in A:
			d[i[0]].append(i[-1])
			d1[i[0]] += 1
			d1[i[-1]] += 1

		def dfs(node):
			v.add(node)
			if node in d:
				for cnode in d[node]:
					if cnode not in v:
						dfs(cnode)
		for i in d:
			if i not in v:
				dfs(i)
				c += 1
		if c > 1:
			return 0
		for i in d1:
			if d1[i] % 2 != 0:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def isCircle(self, N, A):
		store = defaultdict(int)
		adj = defaultdict(list)
		for item in A:
			store[item[0]] += 1
			store[item[-1]] -= 1
			adj[item[0]].append(item[-1])
		if not set(store.values()) == set([0]):
			return 0
		visited = set()
		stack = [A[0][0]]
		while stack:
			node = stack.pop()
			if node in visited:
				continue
			visited.add(node)
			stack += adj[node]
		return int(len(visited) == len(store))


from collections import defaultdict

class Solution:

	def isCircle(self, N, A):
		graph = defaultdict(list)
		degree = defaultdict(int)
		visited = set()
		component_count = 0
		for word in A:
			(start, end) = (word[0], word[-1])
			graph[start].append(end)
			degree[start] += 1
			degree[end] += 1

		def dfs(node):
			visited.add(node)
			if node in graph:
				for neighbor in graph[node]:
					if neighbor not in visited:
						dfs(neighbor)
		for node in graph:
			if node not in visited:
				dfs(node)
				component_count += 1
		if component_count > 1:
			return 0
		for node_degree in degree.values():
			if node_degree % 2 != 0:
				return 0
		return 1


from collections import defaultdict

class Solution:

	@staticmethod
	def dfs(graph, visited, node):
		if visited[node]:
			return len(visited) == len(graph)
		visited[node] = True
		for neighbor in graph[node]:
			if Solution.dfs(graph, visited, neighbor):
				return True
		return False

	def isCircle(self, N, A):
		indegree = defaultdict(int)
		outdegree = defaultdict(int)
		graph = defaultdict(list)
		for word in A:
			first = word[0]
			last = word[-1]
			graph[first].append(last)
			outdegree[first] += 1
			indegree[last] += 1
		for char in set(indegree.keys()).union(outdegree.keys()):
			if indegree[char] != outdegree[char]:
				return 0
		visited = defaultdict(bool)
		return 1 if Solution.dfs(graph, visited, A[0][0]) else 0


from collections import defaultdict

class Solution:

	def dfs(self, node, graph):
		self.visited[node] = 1
		for i in graph[node]:
			if not self.visited[i]:
				self.dfs(i, graph)

	def isCircle(self, N, A):
		self.visited = defaultdict(int)
		graph = defaultdict(list)
		for i in A:
			graph[i[0]].append(i[-1])
			graph[i[-1]].append(i[0])
		for i in graph:
			if len(graph[i]) % 2:
				return 0
		count = -1
		for i in graph:
			if not self.visited[i]:
				self.dfs(i, graph)
				count += 1
			if count:
				return 0
		return 1


def dfs(node, map1, visited):
	temp = map1[node] if node in map1 else []
	if len(temp) == 0:
		return
	visited[node] = 1
	for i in temp:
		if visited[i] == 0:
			dfs(i, map1, visited)

def detectCycle(src, map1, mark):
	visited = [0] * 26
	dfs(src, map1, visited)
	for i in range(26):
		if visited[i] == 0 and mark[i] == 1:
			return 0
	return 1

class Solution:

	def isCircle(self, N, A):
		if N == 1 and A[0][0] != A[0][-1]:
			return 0
		map1 = {}
		mark = [0] * 26
		(ed_in, ed_out) = ([0] * 26, [0] * 26)
		for x in A:
			(u, v) = (ord(x[0]) - ord('a'), ord(x[len(x) - 1]) - ord('a'))
			if u not in map1:
				map1[u] = [v]
			else:
				map1[u].append(v)
			mark[u] = mark[v] = 1
			ed_in[v] += 1
			ed_out[u] += 1
		for i in range(26):
			if ed_in[i] != ed_out[i]:
				return 0
		return detectCycle(ord(A[0][0]) - ord('a'), map1, mark)


class Solution:

	def isCircle(self, N, A):
		a = ord('a')
		V = 26
		graph = [[] for _ in range(V)]
		inv_graph = [[] for _ in range(V)]
		for word in A:
			graph[ord(word[0]) - a].append(ord(word[-1]) - a)
			inv_graph[ord(word[-1]) - a].append(ord(word[0]) - a)
		for i in range(V):
			if len(graph[i]) != len(inv_graph[i]):
				return 0

		def dfs(node, graph, visited):
			visited[node] = True
			for nei in graph[node]:
				if not visited[nei]:
					dfs(nei, graph, visited)

		def checkConnected(graph, node):
			visited = [False] * V
			dfs(node, graph, visited)
			for i in range(V):
				if not visited[i] and len(graph[i]) > 0:
					return False
			return True
		node = 0
		for node in range(V):
			if len(graph[node]) > 0:
				break
		if not checkConnected(graph, node):
			return 0
		if not checkConnected(inv_graph, node):
			return 0
		return 1


class Solution:

	def isCircle(self, N, A):
		adj = [[] for i in range(26)]
		indeg = [0 for i in range(26)]
		for i in A:
			adj[ord(i[0]) - 97].append(ord(i[-1]) - 97)
			indeg[ord(i[-1]) - 97] += 1
		for i in range(26):
			if len(adj[i]) != indeg[i]:
				return 0
		visited = [False for i in range(26)]
		node = ord(A[0][0]) - 97
		self.dfs(node, adj, visited)
		for i in range(26):
			if adj[i] and (not visited[i]):
				return 0
		return 1

	def dfs(self, node, adj, visited):
		visited[node] = True
		for i in adj[node]:
			if not visited[i]:
				self.dfs(i, adj, visited)


from collections import defaultdict

class Solution:

	def isCircle(self, N, A):
		self.graph = defaultdict(lambda : [[], set()])
		word = None
		lenn = 0
		for word in A:
			self.graph[word[0]][0].append(word[-1])
			lenn += 1
		count = 0
		self.queu = [word[0]]
		while self.queu:
			count += self.loop(self.queu[0])[0]
		if count == lenn:
			return 1
		return 0

	def loop(self, start):
		count = 0
		try:
			self.queu.remove(start)
		except:
			pass
		while self.graph[start][0]:
			nexxt = self.graph[start][0].pop()
			if nexxt == start:
				count += 1
				continue
			if nexxt in self.graph[start][1]:
				self.graph[start][1] = set()
				if self.graph[start][0]:
					self.queu.append(start)
				return (count + 1, nexxt)
			self.graph[nexxt][1].add(start)
			self.graph[nexxt][1].update(self.graph[start][1])
			(ncount, nstart) = self.loop(nexxt)
			if nstart is not None and nstart != start:
				self.graph[start][1] = set()
				if self.graph[start][0]:
					self.queu.append(start)
				return (count + ncount + 1, nstart)
			count += ncount
			if not self.graph[nexxt][1]:
				count += 1
		return (count, None)


MAX_CHARS = 26

class Solution:

	def dfs(self, u, adj, visited):
		visited[u] = True
		for v in adj[u]:
			if not visited[v]:
				self.dfs(v, adj, visited)

	def is_all_edges_connected(self, src, adj, mark, V):
		visited = [False] * V
		self.dfs(src, adj, visited)
		for u in range(V):
			if mark[u] and (not visited[u]):
				return False
		return True

	def isCircle(self, N, A):
		V = MAX_CHARS
		adj = {u: [] for u in range(V)}
		In = [0] * V
		out = [0] * V
		mark = [False] * V
		for i in range(N):
			s = A[i]
			f = s[0]
			l = s[-1]
			u = ord(f) - ord('a')
			v = ord(l) - ord('a')
			mark[u] = True
			mark[v] = True
			adj[u].append(v)
			out[u] += 1
			In[v] += 1
		for u in range(V):
			if In[u] != out[u]:
				return 0
		src = ord(A[0][0]) - ord('a')
		if self.is_all_edges_connected(src, adj, mark, V):
			return 1
		return 0


class Solution:

	def DFS(self, adj, start, visited):
		visited[start] = 1
		for ch in adj[start]:
			if visited[ch] == 0:
				self.DFS(adj, ch, visited)

	def CheckLoop(self, adj, characters, start):
		visited = [0] * 26
		self.DFS(adj, start, visited)
		for i in range(26):
			if characters[i] == 1 and visited[i] == 0:
				return False
		return True

	def check(self, N, A):
		characters = [0] * 26
		adj = [[] for i in range(26)]
		indegree = [0] * 26
		outdegree = [0] * 26
		for string in A:
			first = ord(string[0]) - 97
			last = ord(string[len(string) - 1]) - 97
			adj[first].append(last)
			outdegree[first] += 1
			indegree[last] += 1
			characters[first] = 1
			characters[last] = 1
		for i in range(26):
			if indegree[i] != outdegree[i]:
				return False
		return self.CheckLoop(adj, characters, ord(A[0][0]) - 97)

	def isCircle(self, N, A):
		return int(self.check(N, A))


def dfs(g, i):
	global visited
	visited[i] = True
	for j in g[i]:
		if visited[j] == False:
			dfs(g, j)

def Circle(s):
	global visited
	n = len(s)
	mark = [False] * 26
	adj = {i: [] for i in range(26)}
	(indegree, outdegree) = ([0] * 26, [0] * 26)
	for i in s:
		(u, v) = (ord(i[0]) - ord('a'), ord(i[-1]) - ord('a'))
		(mark[u], mark[v]) = (True, True)
		indegree[v] += 1
		outdegree[u] += 1
		adj[u].append(v)
	for i in range(26):
		if indegree[i] != outdegree[i]:
			return 0
	visited = [False] * 26
	dfs(adj, ord(s[0][0]) - ord('a'))
	for i in range(26):
		if visited[i] == 0 and mark[i] == True:
			return 0
	return 1

class Solution:

	def isCircle(self, N, A):
		return Circle(A)


CHARS = 26

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for x in range(V)]
		self.inp = [0] * V

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.inp[w] += 1

	def isSC(self):
		visited = [False] * self.V
		n = 0
		for n in range(self.V):
			if len(self.adj[n]) > 0:
				break
		self.DFSUtil(n, visited)
		for i in range(self.V):
			if len(self.adj[i]) > 0 and visited[i] == False:
				return False
		gr = self.getTranspose()
		for i in range(self.V):
			visited[i] = False
		gr.DFSUtil(n, visited)
		for i in range(self.V):
			if len(self.adj[i]) > 0 and visited[i] == False:
				return False
		return True

	def isEulerianCycle(self):
		if self.isSC() == False:
			return False
		for i in range(self.V):
			if len(self.adj[i]) != self.inp[i]:
				return False
		return True

	def DFSUtil(self, v, visited):
		visited[v] = True
		for i in range(len(self.adj[v])):
			if not visited[self.adj[v][i]]:
				self.DFSUtil(self.adj[v][i], visited)

	def getTranspose(self):
		g = Graph(self.V)
		for v in range(self.V):
			for i in range(len(self.adj[v])):
				g.adj[self.adj[v][i]].append(v)
				g.inp[v] += 1
		return g

def canBeChained(arr, n):
	g = Graph(CHARS)
	for i in range(n):
		s = arr[i]
		g.addEdge(ord(s[0]) - ord('a'), ord(s[len(s) - 1]) - ord('a'))
	return int(g.isEulerianCycle())


class Solution:

	def isCircle(self, N, A):
		(adj, wcnt, vis, c) = ({}, {}, set(), 0)
		for w in A:
			if w[0] not in adj:
				adj[w[0]] = [w[-1]]
			else:
				adj[w[0]].append(w[-1])
			if w[0] not in wcnt:
				wcnt[w[0]] = 1
			else:
				wcnt[w[0]] += 1
			if w[-1] not in wcnt:
				wcnt[w[-1]] = 1
			else:
				wcnt[w[-1]] += 1

		def dfs(x):
			vis.add(x)
			if x in adj:
				for ele in adj[x]:
					if ele not in vis:
						dfs(ele)
		for k in adj:
			if k not in vis:
				dfs(k)
				c += 1
		if c > 1:
			return 0
		for u in wcnt:
			if wcnt[u] % 2 != 0:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def isCircle(self, N, A):
		indegree = [0] * 26
		graph = [[] for _ in range(26)]
		mark = [0] * 26
		for i in range(N):
			s = A[i]
			(u, v) = (ord(s[0]) - 97, ord(s[-1]) - 97)
			indegree[v] += 1
			graph[u].append(v)
			mark[u] = 1
			mark[v] = 1
		for i in range(26):
			if indegree[i] != len(graph[i]):
				return 0
		visited = [0] * 26

		def dfs(start):
			visited[start] = 1
			for j in graph[start]:
				if visited[j] == 0:
					dfs(j)
		dfs(ord(A[0][0]) - 97)
		for i in range(26):
			if visited[i] == 0 and mark[i]:
				return 0
		return 1


CHARS = 26

class Graph(object):

	def __init__(self, V):
		self.V = V
		self.adj = [[] for x in range(V)]
		self.inp = [0] * V

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.inp[w] += 1

	def isSC(self):
		visited = [0] * self.V
		n = 0
		for n in range(self.V):
			if len(self.adj[n]) > 0:
				break
		self.DFSUtil(n, visited)
		for i in range(self.V):
			if len(self.adj[i]) > 0 and visited[i] == 0:
				return 0
		gr = self.getTranspose()
		for i in range(self.V):
			visited[i] = 0
		gr.DFSUtil(n, visited)
		for i in range(self.V):
			if len(self.adj[i]) > 0 and visited[i] == 0:
				return 0
		return 1

	def isEulerianCycle(self):
		if self.isSC() == 0:
			return 0
		for i in range(self.V):
			if len(self.adj[i]) != self.inp[i]:
				return 0
		return 1

	def DFSUtil(self, v, visited):
		visited[v] = 1
		for i in range(len(self.adj[v])):
			if not visited[self.adj[v][i]]:
				self.DFSUtil(self.adj[v][i], visited)

	def getTranspose(self):
		g = Graph(self.V)
		for v in range(self.V):
			for i in range(len(self.adj[v])):
				g.adj[self.adj[v][i]].append(v)
				g.inp[v] += 1
		return g

class Solution:

	def isCircle(self, n, arr):
		g = Graph(CHARS)
		for i in range(n):
			s = arr[i]
			g.addEdge(ord(s[0]) - ord('a'), ord(s[len(s) - 1]) - ord('a'))
		return g.isEulerianCycle()


class Graph:

	def __init__(self):
		self.adj = [[] for i in range(26)]
		self.in_degree = [0 for i in range(26)]
		self.out_degree = [0 for i in range(26)]
		self.no_vertices = 26

class Solution:

	def DFS(self, node, adj_lst, visited):
		visited[node] = True
		for ch in adj_lst[node]:
			if not visited[ch]:
				self.DFS(ch, adj_lst, visited)

	def get_transpose(self, adj_lst):
		trans_graph = Graph()
		for i in range(0, len(adj_lst)):
			for j in range(0, len(adj_lst[i])):
				trans_graph.adj[adj_lst[i][j]].append(i)
		return trans_graph

	def is_a_single_component(self, N, graph_obj):
		adj_lst = graph_obj.adj
		visited = [False for i in range(graph_obj.no_vertices)]
		node = -1
		for indx in range(0, len(adj_lst)):
			if len(adj_lst[indx]) > 0:
				node = indx
				break
		if node == -1:
			return False
		self.DFS(indx, adj_lst, visited)
		for indx in range(0, len(visited)):
			if visited[indx] == False and len(adj_lst[indx]) > 0:
				return False
		for i in range(0, len(visited)):
			visited[i] = False
		trans_graph = self.get_transpose(adj_lst)
		self.DFS(node, trans_graph.adj, visited)
		for indx in range(0, len(visited)):
			if visited[indx] == False and len(adj_lst[indx]) > 0:
				return False
		return True

	def add_edge(self, adj_lst, a, b):
		adj_lst[a].append(b)

	def isCircle(self, N, A):
		graph_obj = Graph()
		for i in range(0, N):
			st = ord(A[i][0]) - ord('a')
			end = ord(A[i][len(A[i]) - 1]) - ord('a')
			self.add_edge(graph_obj.adj, st, end)
			graph_obj.in_degree[st] += 1
			graph_obj.out_degree[end] += 1
		if not self.is_a_single_component(N, graph_obj):
			return 0
		for i in range(26):
			if graph_obj.in_degree[i] != graph_obj.out_degree[i]:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def dfs(self, visited, v, adj):
		visited.add(v)
		if v in adj:
			for i in adj[v]:
				if i not in visited:
					self.dfs(visited, i, adj)

	def connected(self, V, adj):
		visited = set()
		cou = 0
		for v in adj:
			if v not in visited:
				self.dfs(visited, v, adj)
				cou += 1
		if cou > 1:
			return False
		return True

	def iseuler(self, V, adj, inde):
		if self.connected(V, adj) == False:
			return 0
		for i in inde:
			if inde[i] % 2 != 0:
				return 0
		return 1

	def isCircle(self, N, A):
		adj = defaultdict(list)
		inde = defaultdict(int)
		for i in A:
			inde[i[-1]] += 1
			inde[i[0]] += 1
			adj[i[0]].append(i[-1])
		return self.iseuler(N, adj, inde)


from collections import defaultdict

class Solution:

	def isCircle(self, N, A):
		inDeg = dict()
		outDeg = dict()
		graph = defaultdict(list)
		visited = set()

		def dfs(u):
			visited.add(u)
			for v in graph[u]:
				if v not in visited:
					dfs(v)
		for str in A:
			inDeg[str[0]] = inDeg.get(str[0], 0) + 1
			outDeg[str[-1]] = outDeg.get(str[-1], 0) + 1
			graph[str[0]].append(str[-1])
		for (key, val) in inDeg.items():
			if val != outDeg.get(key, 0):
				return 0
		dfs(A[0][0])
		for ch in A:
			if ch[0] not in visited or ch[-1] not in visited:
				return 0
		return 1


CHARS = 26

class Graph(object):

	def __init__(self, V):
		self.V = V
		self.adj = [[] for x in range(V)]
		self.inp = [0] * V

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.inp[w] += 1

	def isEulerianCycle(self):
		if self.isSconnected() == False:
			return False
		for i in range(self.V):
			if len(self.adj[i]) != self.inp[i]:
				return False
		return True

	def isSconnected(self):
		visited = [False] * self.V
		n = 0
		for n in range(self.V):
			if len(self.adj[n]) > 0:
				break
		self.DFS(n, visited)
		for i in range(self.V):
			if len(self.adj[i]) > 0 and visited[i] == False:
				return False
		gr = self.getTranspose()
		visited = [False] * self.V
		gr.DFS(n, visited)
		for i in range(self.V):
			if len(self.adj[i]) > 0 and visited[i] == False:
				return False
		return True

	def DFS(self, v, visited):
		visited[v] = True
		for i in self.adj[v]:
			if visited[i] == False:
				self.DFS(i, visited)

	def getTranspose(self):
		g = Graph(self.V)
		for v in range(self.V):
			for i in range(len(self.adj[v])):
				g.adj[self.adj[v][i]].append(v)
				g.inp[v] += 1
		return g

class Solution:

	def isCircle(self, N, A):
		g = Graph(CHARS)
		for i in range(N):
			s = A[i]
			g.addEdge(ord(s[0]) - ord('a'), ord(s[len(s) - 1]) - ord('a'))
		return 1 if g.isEulerianCycle() else 0


def dfs(adj, u, vis):
	vis[u] = 1
	for i in adj[u]:
		if vis[i] == 0:
			dfs(adj, i, vis)

class Solution:

	def isCircle(self, N, A):
		adj = [[] for i in range(26)]
		adj_reverse = [[] for i in range(26)]
		for s in A:
			u = ord(s[0]) - ord('a')
			v = ord(s[-1]) - ord('a')
			adj[u].append(v)
			adj_reverse[v].append(u)
		indeg = [0] * 26
		for i in range(26):
			for j in adj[i]:
				indeg[j] += 1
		for i in range(26):
			if len(adj[i]) and len(adj[i]) != indeg[i]:
				return 0
		n = 0
		for i in range(26):
			if indeg[i]:
				n = i
				break
		vis = [0] * 26
		dfs(adj, n, vis)
		for i in range(26):
			if vis[i] == 0 and len(adj_reverse[i]):
				return 0
		return 1


class Solution:

	def __init__(self):
		self.V = 26
		self.adj = [[] for x in range(26)]
		self.inp = [0] * 26

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.inp[w] += 1

	def isSC(self):
		visited = [False] * self.V
		n = 0
		for n in range(self.V):
			if len(self.adj[n]) > 0:
				break
		self.DFSUtil(n, visited)
		for i in range(self.V):
			if len(self.adj[i]) > 0 and visited[i] == False:
				return False
		gr = self.getTranspose()
		for i in range(self.V):
			visited[i] = False
		gr.DFSUtil(n, visited)
		for i in range(self.V):
			if len(self.adj[i]) > 0 and visited[i] == False:
				return False
		return True

	def isEulerianCycle(self):
		if self.isSC() == False:
			return False
		for i in range(self.V):
			if len(self.adj[i]) != self.inp[i]:
				return False
		return True

	def DFSUtil(self, v, visited):
		visited[v] = True
		for i in range(len(self.adj[v])):
			if not visited[self.adj[v][i]]:
				self.DFSUtil(self.adj[v][i], visited)

	def getTranspose(self):
		g = Solution()
		for v in range(self.V):
			for i in range(len(self.adj[v])):
				g.adj[self.adj[v][i]].append(v)
				g.inp[v] += 1
		return g

	def isCircle(self, N, A):
		g = Solution()
		for i in range(N):
			s = A[i]
			g.addEdge(ord(s[0]) - ord('a'), ord(s[len(s) - 1]) - ord('a'))
		if g.isEulerianCycle():
			return 1
		else:
			return 0


from collections import Counter

class Solution:

	def isCircle(self, N, A):
		c0 = Counter((a[0] for a in A))
		c1 = Counter((a[-1] for a in A))
		if c0 != c1:
			return 0
		d = {}
		for a in A:
			d.setdefault(a[0], set()).add(a[-1])
		(r, *_) = d
		q = {r}
		done = set()
		while q:
			r = q.pop()
			done.add(r)
			q.update(d[r] - done)
		return 1 if done == set(d) else 0


from collections import defaultdict

class Solution:

	def isCircle(self, N, A):
		A = list(A)

		def dfs(g, vis, u):
			vis[u] = 1
			for nei in g[u]:
				if not vis[nei]:
					dfs(g, vis, nei)
		vis = defaultdict(int)
		g = defaultdict(list)
		for i in range(N):
			g[A[i][0]].append(A[i][-1])
			g[A[i][-1]].append(A[i][0])
		count = 0
		for (k, v) in g.items():
			if not vis[k]:
				dfs(g, vis, k)
				count += 1
		if count > 1:
			return 0
		for (k, v) in g.items():
			if len(v) & 1:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def DFS(self, src, adj, visited):
		visited[src] = True
		for nbr in adj[src]:
			if not visited[nbr]:
				self.DFS(nbr, adj, visited)

	def isConnected(self, src, adj, mark):
		visited = [False] * 26
		self.DFS(src, adj, visited)
		for i in range(26):
			if visited[i] == False and mark[i] == True:
				return 0
		return 1

	def isCircle(self, N, A):
		mark = [False] * 26
		adj = [[] for _ in range(26)]
		indegree = [0] * 26
		outdegree = [0] * 26
		for i in range(N):
			u = ord(A[i][0]) - ord('a')
			v = ord(A[i][-1]) - ord('a')
			mark[u] = mark[v] = True
			adj[u].append(v)
			indegree[v] += 1
			outdegree[u] += 1
		for i in range(26):
			if indegree[i] != outdegree[i]:
				return 0
		return self.isConnected(ord(A[0][0]) - ord('a'), adj, mark)


class Solution:

	def kosaraju(self, V, adj):
		badj = [None] * V
		for i in adj:
			badj[i] = list(adj[i])
		adj = badj

		def trans(adj, V):
			tr = {}
			for (i, val) in enumerate(adj):
				if val:
					for V in val:
						if V not in tr:
							tr[V] = [i]
						else:
							tr[V].append(i)
			return tr

		def dfs(u):
			vi[u] = 1
			v = adj[u]
			if v:
				for V in v:
					if not vi[V]:
						dfs(V)
				st.append(u)

		def dfs_(u):
			if c[0] not in ans:
				ans[c[0]] = [u]
			else:
				ans[c[0]].append(u)
			vi[u] = 1
			if u in adj:
				v = adj[u]
				for V in v:
					if not vi[V]:
						dfs(V)
		vi = [0] * V
		st = []
		for i in range(V):
			if not vi[i]:
				dfs(i)
		nadj = trans(adj, V)
		adj = nadj
		vi = [0] * V
		c = [0]
		ans = {}
		for i in st[::-1]:
			if not vi[i]:
				dfs_(i)
				c[0] += 1
		return c[0]

	def isCircle(self, N, A):

		def graph(A):
			adj = {}
			ind = [0] * 26
			out = [0] * 26
			for i in A:
				if ord(i[0]) - ord('a') in adj:
					adj[ord(i[0]) - ord('a')].add(ord(i[-1]) - ord('a'))
				else:
					adj[ord(i[0]) - ord('a')] = set([ord(i[-1]) - ord('a')])
				ind[ord(i[-1]) - ord('a')] += 1
				out[ord(i[0]) - ord('a')] += 1
			c = len(adj)
			return (adj, ind, out, c)
		(adj, ind, out, v) = graph(A)
		c = self.kosaraju(26, adj)

		def degcheck():
			for i in range(26):
				if ind[i] != out[i]:
					return False
			return True
		flag = degcheck()
		if c == 1 and flag:
			return 1
		return 0


import collections

class Solution:

	def isCircle(self, N, A):
		g = collections.defaultdict(list)
		d1 = collections.defaultdict(int)
		visited = set()
		count = 0
		for i in A:
			g[i[0]].append(i[-1])
			d1[i[0]] += 1
			d1[i[-1]] += 1

		def dfs(node):
			visited.add(node)
			if node in g:
				for child in g[node]:
					if child not in visited:
						dfs(child)
		for i in g:
			if i not in visited:
				dfs(i)
				count += 1
		if count > 1:
			return 0
		for i in d1:
			if d1[i] % 2 != 0:
				return 0
		return 1


class Solution:

	def conn(self, node, adj):
		ref_ver[node] = True
		if node in adj:
			for x in adj[node]:
				if not ref_ver[x]:
					self.conn(x, adj)
		return

	def isCircle(self, N, A):
		global ref_ver
		adj = {}
		ref_ver = {}
		ref_in = {}
		ref_out = {}
		count = 0
		for x in A:
			ref_ver[x[0]] = False
			ref_ver[x[-1]] = False
			if x[0] not in adj:
				adj[x[0]] = [x[-1]]
			else:
				adj[x[0]].append(x[-1])
			if x[0] not in ref_out:
				ref_out[x[0]] = 1
			else:
				ref_out[x[0]] += 1
			if x[-1] not in ref_in:
				ref_in[x[-1]] = 1
			else:
				ref_in[x[-1]] += 1
		for x in ref_out:
			if x not in ref_in:
				return 0
			elif ref_in[x] != ref_out[x]:
				return 0
		for x in ref_ver:
			if not ref_ver[x]:
				self.conn(x, adj)
				count += 1
		if count == 1:
			return 1
		else:
			return 0
		print(adj, ref_ver)


class Solution:

	def isCircle(self, N, A):

		def dfs(node, vis, d):
			vis[node] = 1
			for ele in d[node]:
				if not vis[ele]:
					dfs(ele, vis, d)
		alp = 'abcdefghijklmnopqrstuvwxyz'
		d = {}
		for i in range(N):
			if A[i][0] not in d:
				d[A[i][0]] = [A[i][-1]]
			else:
				d[A[i][0]] += [A[i][-1]]
			if A[i][-1] not in d:
				d[A[i][-1]] = [A[i][0]]
			else:
				d[A[i][-1]] += [A[i][0]]
		vis = {}
		for ele in alp:
			vis[ele] = 0
		cnt = 0
		for ele in alp:
			if not vis[ele] and ele in d:
				dfs(ele, vis, d)
				cnt += 1
		if cnt > 1:
			return 0
		for ele in alp:
			if ele in d:
				if len(d[ele]) % 2:
					return 0
		return 1


class Graph:

	def __init__(self, v):
		self.v = v
		self.adj = [[] for i in range(v)]
		self.inp = [0] * v

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.inp[w] += 1

	def DFSUtil(self, v, visited):
		visited[v] = True
		for i in self.adj[v]:
			if not visited[i]:
				self.DFSUtil(i, visited)

	def getTranspose(self):
		g = Graph(self.v)
		for v in range(self.v):
			for i in range(len(self.adj[v])):
				g.adj[self.adj[v][i]].append(v)
				g.inp[v] += 1
		return g

	def isSC(self):
		visited = [False] * self.v
		n = 0
		for n in range(self.v):
			if len(self.adj[n]) > 0:
				break
		self.DFSUtil(n, visited)
		for i in range(self.v):
			if len(self.adj[i]) > 0 and visited[i] == False:
				return False
		gr = self.getTranspose()
		for i in range(self.v):
			visited[i] = False
		gr.DFSUtil(n, visited)
		for i in range(self.v):
			if len(self.adj[i]) > 0 and visited[i] == False:
				return False
		return True

	def isEulerianCycle(self):
		if self.isSC() == False:
			return False
		for i in range(self.v):
			if len(self.adj[i]) != self.inp[i]:
				return False
		return True

class Solution:

	def isCircle(self, n, arr):
		g = Graph(26)
		for i in range(n):
			s = arr[i]
			g.addEdge(ord(s[0]) - ord('a'), ord(s[-1]) - ord('a'))
		if g.isEulerianCycle():
			return 1
		return 0
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = input().split()
		ob = Solution()
		print(ob.isCircle(N, A))


from collections import defaultdict

class Solution:

	def isCircle(self, N, A):
		(d, d1, v, c) = (defaultdict(list), defaultdict(int), set(), 0)
		for i in A:
			d[i[0]].append(i[-1])
			d1[i[0]] += 1
			d1[i[-1]] += 1

		def dfs(node):
			v.add(node)
			if node in d:
				for cnode in d[node]:
					if cnode not in v:
						dfs(cnode)
		for i in d:
			if i not in v:
				dfs(i)
				c += 1
		if c > 1:
			return 0
		for i in d1:
			if d1[i] % 2 != 0:
				return 0
		return 1
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = input().split()
		ob = Solution()
		print(ob.isCircle(N, A))


class Solution:

	def dfs(self, node, adj, vis):
		vis[node] = True
		for u in adj[node]:
			if vis[u] == False:
				self.dfs(u, adj, vis)

	def isCircle(self, N, A):
		adj = [[] for i in range(26)]
		adjr = [[] for i in range(26)]
		for i in range(N):
			x = len(A[i]) - 1
			adj[ord(A[i][0]) - ord('a')].append(ord(A[i][x]) - ord('a'))
			adjr[ord(A[i][x]) - ord('a')].append(ord(A[i][0]) - ord('a'))
		indeg = [0 for i in range(26)]
		for i in range(26):
			if len(adj[i]):
				for u in adj[i]:
					indeg[u] = indeg[u] + 1
		for i in range(26):
			if len(adj[i]) > 0 and indeg[i] != len(adj[i]):
				return 0
		visited = [False for i in range(26)]
		n = 0
		for i in range(26):
			if indeg[i]:
				n = i
				break
		self.dfs(n, adj, visited)
		for i in range(26):
			if visited[i] == False and len(adjr[i]):
				return 0
		return 1
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = input().split()
		ob = Solution()
		print(ob.isCircle(N, A))


class Solution:

	def isCircle(self, N, A):
		adj = [[] for i in range(26)]
		deg = [0] * 26
		diff = 97
		dic = {}
		c = 0
		for i in range(N):
			inx = ord(A[i][0]) - diff
			if inx not in dic:
				dic[inx] = 1
				c += 1
			n = len(A[i])
			adj[inx].append(A[i][n - 1])
			adj[ord(A[i][n - 1]) - diff].append(A[i][0])
		visited = [0] * 26
		stack = [0] * 26

		def dfs(i):
			visited[i] = 1
			for k in adj[i]:
				if visited[ord(k) - diff] == 0:
					dfs(ord(k) - diff)
		count = 0
		for i in range(26):
			if visited[i] == 0 and adj[i]:
				dfs(i)
				count += 1
		if count > 1:
			return 0
		for i in range(26):
			if len(adj[i]) % 2 == 1:
				return 0
		return 1
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = input().split()
		ob = Solution()
		print(ob.isCircle(N, A))


class Solution:

	def isCircle(self, N, A):
		graph = [[] for k in range(26)]
		indegree = [0] * 26
		for el in A:
			graph[ord(el[0]) - ord('a')].append(ord(el[-1]) - ord('a'))
			indegree[ord(el[-1]) - ord('a')] += 1
		visited = [False] * 26
		trans = [[] for k in range(26)]

		def dfs1(v):
			visited[v] = True
			for k in graph[v]:
				if visited[k] == False:
					dfs1(k)

		def transpose():
			for el in A:
				trans[ord(el[-1]) - ord('a')].append(ord(el[0]) - ord('a'))
		for v in range(26):
			if len(graph[v]) > 0:
				dfs1(v)
				break
		for v in range(26):
			if len(graph[v]) and visited[v] == False:
				return 0
		transpose()
		visited = [False for k in range(26)]
		for v in range(26):
			if len(trans[v]) > 0:
				dfs1(v)
				break
		for v in range(26):
			if len(trans[v]) and visited[v] == False:
				return 0
		for v in range(26):
			if indegree[v] != len(graph[v]):
				return 0
		return 1
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = input().split()
		ob = Solution()
		print(ob.isCircle(N, A))


class Solution:

	def dfs(self, adj, n, vis):
		vis[n] = 1
		for node in adj[n]:
			if vis[node] == 0:
				self.dfs(adj, node, vis)

	def sc(self, v, adj):
		vis = [False] * v
		for n in range(v):
			if len(adj[n]) > 0:
				break
		self.dfs(adj, n, vis)
		for i in range(v):
			if len(adj[i]) > 0 and vis[i] == False:
				return False
		newAdj = [[] for i in range(v)]
		for i in range(v):
			for node in adj[i]:
				newAdj[node].append(i)
		for i in range(v):
			vis[i] = False
		self.dfs(newAdj, n, vis)
		for i in range(v):
			if len(newAdj[i]) > 0 and vis[i] == False:
				return False
		return True

	def isCircle(self, n, A):
		v = 26
		adj = [[] for i in range(26)]
		inp = [0] * 26
		for s in A:
			(ind1, ind2) = (ord(s[0]) - ord('a'), ord(s[len(s) - 1]) - ord('a'))
			adj[ind1].append(ind2)
			inp[ind2] += 1
		if self.sc(v, adj) == False:
			return 0
		for i in range(v):
			if len(adj[i]) != inp[i]:
				return 0
		return 1
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = input().split()
		ob = Solution()
		print(ob.isCircle(N, A))


from collections import defaultdict

class Solution:

	def isCircle(self, N, A):
		graph = defaultdict(list)
		ind = defaultdict(int)
		outd = defaultdict(int)
		seen = {chr(i): False for i in range(ord('a'), ord('a') + 26)}
		for word in A:
			graph[word[0]].append(word[-1])
			ind[word[-1]] += 1
			outd[word[0]] += 1
		for i in range(ord('a'), ord('a') + 26):
			if ind[chr(i)] != outd[chr(i)]:
				return 0

		def dfs(u):
			seen[u] = True
			for v in graph[u]:
				if not seen[v]:
					dfs(v)
		flag = False
		for i in range(ord('a'), ord('a') + 26):
			if ind[chr(i)] != 0 and (not seen[chr(i)]):
				if flag:
					return 0
				flag = True
				dfs(chr(i))
		return 1
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = input().split()
		ob = Solution()
		print(ob.isCircle(N, A))


from collections import defaultdict

class Solution:

	def isCircle(self, N, A):
		graph = defaultdict(list)
		char_count = defaultdict(int)
		for word in A:
			graph[word[0]].append(word[-1])
			char_count[word[0]] += 1
			char_count[word[-1]] += 1
		visited = set()
		cycle = 0
		for vertex in graph:
			if vertex not in visited:
				self.dfs(vertex, visited, graph)
				cycle += 1
		if cycle > 1:
			return 0
		for char in char_count:
			if char_count[char] % 2 != 0:
				return 0
		return 1

	def dfs(self, node, visited, graph):
		visited.add(node)
		if node in graph:
			for vertex in graph[node]:
				if vertex not in visited:
					self.dfs(vertex, visited, graph)
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = input().split()
		ob = Solution()
		print(ob.isCircle(N, A))


class Solution:

	def getT(adj):
		tpg = [[] for i in range(26)]
		for i in range(26):
			for j in adj[i]:
				tpg[j].append(i)
		return tpg

	def bfs(adj, visited, i):
		visited[i] = True
		for j in adj[i]:
			if visited[j] == False:
				Solution.bfs(adj, visited, j)

	def isCircle(self, N, A):
		adj = [[] for i in range(26)]
		indeg = [0 for i in range(26)]
		for word in A:
			i = ord(word[0]) % 26
			j = ord(word[-1]) % 26
			adj[i].append(j)
			indeg[j] += 1
		tpg = Solution.getT(adj)
		visited = [False for i in range(26)]
		n = 0
		for i in range(26):
			if len(tpg[i]) > 0:
				n = i
				break
		Solution.bfs(tpg, visited, n)
		for i in range(26):
			if len(tpg[i]) > 0 and visited[i] == False:
				return 0
		visited = [False for i in range(26)]
		Solution.bfs(adj, visited, n)
		for i in range(26):
			if len(adj[i]) > 0 and visited[i] == False:
				return 0
		for i in range(26):
			if len(adj[i]) != indeg[i]:
				return 0
		return 1
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = input().split()
		ob = Solution()
		print(ob.isCircle(N, A))


class Solution:

	def isCircle(self, N, A):
		graph = dict()
		for string in A:
			src = string[0]
			dest = string[-1]
			if src in graph:
				graph[src].append(dest)
			else:
				graph[src] = [dest]
		degrees = dict()
		for string in A:
			src = string[0]
			dest = string[-1]
			if src in degrees:
				temp = (degrees[src][0] + 1, degrees[src][1])
				degrees[src] = temp
			else:
				degrees[src] = (1, 0)
			if dest in degrees:
				temp = (degrees[dest][0], degrees[dest][1] + 1)
				degrees[dest] = temp
			else:
				degrees[dest] = (0, 1)
		for (vertex, (inDeg, outDeg)) in degrees.items():
			if inDeg != outDeg:
				return 0
		visited = dict()
		for vertex in graph.keys():
			visited[vertex] = False
		srcVertex = A[0][0]

		def dfs(srcVertex):
			visited[srcVertex] = True
			for ngh in graph[srcVertex]:
				if visited[ngh] == False:
					dfs(ngh)
		dfs(srcVertex)
		for vertex in visited.keys():
			if visited[vertex] == False:
				return 0
		return 1


class Solution:

	def isCircle(self, N, A):
		adj = [[] for i in range(26)]
		isVisited = [False] * 26
		vertexSet = set()
		inDegree = [0] * 26
		outDegree = [0] * 26
		for str in A:
			start = ord(str[0]) - 97
			end = ord(str[len(str) - 1]) - 97
			vertexSet.add(start)
			vertexSet.add(end)
			inDegree[end] += 1
			outDegree[start] += 1
			adj[start].append(end)
		startPoint = 0
		for i in range(26):
			if inDegree[i] != outDegree[i]:
				return 0
		for i in range(26):
			if len(adj[i]) != 0:
				startPoint = i
		self.dfs(adj, isVisited, startPoint)
		visitedNum = 0
		for i in range(26):
			if isVisited[i]:
				visitedNum += 1
		return 0 if visitedNum != len(vertexSet) else 1

	def dfs(self, adj, isVisited, startPoint):
		isVisited[startPoint] = True
		for num in adj[startPoint]:
			if not isVisited[num]:
				self.dfs(adj, isVisited, num)


class Solution:

	def isCircle(self, N, A):
		adj = dict()
		in_out_count = dict()
		for node in A:
			fl = node[0]
			ll = node[-1]
			if adj.get(fl):
				adj[fl].append(ll)
			else:
				adj[fl] = [ll]
			if not adj.get(ll):
				adj[ll] = []
			in_out_count[fl] = in_out_count.get(fl, 0) + 1
			in_out_count[ll] = in_out_count.get(ll, 0) - 1
		visited = {}
		for key in adj.keys():
			visited[key] = False
		self.performDFS(key, adj, visited)
		for key in visited.keys():
			if visited[key] == False:
				return 0
		for key in in_out_count.keys():
			if in_out_count[key] != 0:
				return 0
		return 1

	def performDFS(self, sv, adj, visited):
		visited[sv] = True
		for a in adj[sv]:
			if visited[a] is False:
				self.performDFS(a, adj, visited)
		return


class Solution:

	def isCircle(self, N, A):
		start = {}
		end = {}
		same_letter = {}
		for string in A:
			(start_letter, end_letter) = (string[0], string[-1])
			if start_letter == end_letter:
				if start_letter not in same_letter:
					same_letter[start_letter] = 0
				same_letter[start_letter] += 1
			else:
				if start_letter not in start:
					start[start_letter] = 0
				if end_letter not in end:
					end[end_letter] = 0
				start[start_letter] += 1
				end[end_letter] += 1
		if len(same_letter) == 1 and (not start) and (not end):
			return 1
		for letter in same_letter:
			if letter not in start:
				return 0
		return int(start == end)


class Solution:

	def isCircle(self, N, A):

		def dfs(visited, v, adj):
			visited[v] = True
			for i in adj[v]:
				if not visited[i]:
					dfs(visited, i, adj)

		def isconnected(adj, mark, v):
			visited = [False] * 26
			dfs(visited, v, adj)
			for i in range(26):
				if mark[i] and (not visited[i]):
					return 0
			return 1
		adj = {}
		mark = [False] * 26
		In = [0] * 26
		Out = [0] * 26
		for i in range(N):
			f = ord(A[i][0]) - ord('a')
			l = ord(A[i][-1]) - ord('a')
			(mark[f], mark[l]) = (True, True)
			if f not in adj:
				adj[f] = []
			adj[f].append(l)
			In[l] += 1
			Out[f] += 1
		for i in range(26):
			if In[i] != Out[i]:
				return 0
		return isconnected(adj, mark, ord(A[0][0]) - ord('a'))


class Solution:

	def dfs(self, u, adj, vis, stack):
		vis[u] = 0
		for v in adj[u]:
			if vis[v] == -1:
				self.dfs(v, adj, vis, stack)
		return vis

	def kosaraju(self, V, adj, marked, st):
		vis = [-1] * V
		vis = self.dfs(st, adj, vis, [])
		for u in range(V):
			if vis[u] == -1 and marked[u] == 1:
				return False
		return True

	def isCircle(self, n, a):
		from collections import defaultdict
		adj = [[] for _ in range(26)]
		indeg = defaultdict(int)
		outdeg = defaultdict(int)
		marked = defaultdict(int)
		for i in range(n):
			st = ord(a[i][0]) - ord('a')
			en = ord(a[i][-1]) - ord('a')
			adj[st].append(en)
			indeg[en] += 1
			outdeg[st] += 1
			marked[st] = 1
			marked[en] = 1
		for i in range(26):
			if indeg[i] != outdeg[i]:
				return 0
		return int(self.kosaraju(26, adj, marked, st))


class Graph(object):

	def __init__(self, V):
		self.V = V
		self.adj = [[] for x in range(V)]
		self.inp = [0 for _ in range(V)]

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.inp[w] += 1

	def isEulerCycle(self):
		if not self.isSC():
			return False
		for i in range(self.V):
			if len(self.adj[i]) != self.inp[i]:
				return False
		return True

	def isSC(self):
		visited = [False for _ in range(self.V)]
		n = 0
		while n < self.V:
			if len(self.adj[n]) > 0:
				break
			n += 1
		self.DFSUtil(n, visited)
		for i in range(self.V):
			if len(self.adj[i]) > 0 and (not visited[i]):
				return False
		reverse_graph = self.getTranspose()
		visited = [False for _ in range(self.V)]
		reverse_graph.DFSUtil(n, visited)
		for i in range(self.V):
			if len(self.adj[i]) > 0 and (not visited[i]):
				return False
		return True

	def DFSUtil(self, vertex, visited):
		visited[vertex] = True
		for nextVertex in self.adj[vertex]:
			if not visited[nextVertex]:
				self.DFSUtil(nextVertex, visited)

	def getTranspose(self):
		newGraph = Graph(self.V)
		for (parentVertex, curAdj) in enumerate(self.adj):
			for childVertex in curAdj:
				newGraph.addEdge(childVertex, parentVertex)
		return newGraph

class Solution:

	def isCircle(self, N, string_arr):
		NCHAR = 26
		graph = Graph(NCHAR)
		for string in string_arr:
			graph.addEdge(ord(string[0]) - ord('a'), ord(string[-1]) - ord('a'))
		return 1 if graph.isEulerCycle() else 0


class Solution:

	def isCircle(self, N, A):
		endswith = {}
		startswith = {}
		first_pal = set()
		for string in A:
			start = string[0]
			end = string[-1]
			if start == end:
				first_pal.add(start)
				continue
			startswith[start] = startswith.get(start, 0) + 1
			endswith[end] = endswith.get(end, 0) + 1
		for (char, freq) in endswith.items():
			if freq != startswith.get(char, 0):
				return 0
		if len(startswith) == 0:
			if len(first_pal) <= 1:
				return 1
			return 0
		for item in first_pal:
			if item not in startswith:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def isCircle(self, N, A):
		self.graph = defaultdict(list)
		self.transposed_graph = defaultdict(list)
		self.vertices = set()
		self.indegree = {}
		return self.iseuleriancycle(A)

	def add_edges(self, A):
		for word in A:
			edges = [char for char in word]
			if len(edges) == 1:
				if edges[0] not in self.graph:
					self.graph[edges[0]] = []
					self.vertices.add(edges[0])
					if edges[0] not in self.indegree:
						self.indegree[edges[0]] = 0
			else:
				src = edges[0]
				dest = edges[-1]
				if src not in self.graph:
					self.graph[src] = [dest]
				else:
					self.graph[src].append(dest)
				self.vertices.add(src)
				self.vertices.add(dest)
				if src not in self.indegree:
					self.indegree[src] = 0
				if dest not in self.indegree:
					self.indegree[dest] = 1
				else:
					self.indegree[dest] += 1

	def dfs(self, node, visited, graph):
		visited[node] = True
		for edge in graph[node]:
			if not visited[edge]:
				self.dfs(edge, visited, graph)

	def transpose(self):
		for (vertex, edges) in self.graph.items():
			for edge in edges:
				if edge not in self.transposed_graph:
					self.transposed_graph[edge] = [vertex]
				else:
					self.transposed_graph[edge].append(vertex)

	def isconnected(self, A):
		self.add_edges(A)
		visited = {v: False for v in self.vertices}
		import random
		start_vertex = random.choice(list(visited))
		self.dfs(start_vertex, visited, self.graph)
		for v in visited:
			if not visited[v]:
				return 0
		self.transpose()
		visited = {v: False for v in self.vertices}
		self.dfs(start_vertex, visited, self.transposed_graph)
		for v in visited:
			if not visited[v]:
				return 0
		return 1

	def iseuleriancycle(self, A):
		if self.isconnected(A) == 0:
			return 0
		for v in self.graph:
			if len(self.graph[v]) != self.indegree[v]:
				return 0
		return 1