Given a Undirected Graph with V vertices and E edges, Find the level of node X. if X does not exist in the graph then print -1.
Note: Traverse the graph starting from vertex 0.
  
Example 1:
Input:
X = 4
Output:
2
Explanation:
We can clearly see that Node 4 lies at Level 2.
Example 2:
Input:
X = 5
Output:
-1
Explanation:
Node 5 isn't present in the Graph, so the
Output is -1.
 
Your task:
You dont need to read input or print anything. Your task is to complete the function nodeLevel() which takes two integers V and X denoting the number of vertices and the node, and another adjacency list adj as input parameters and returns the level of Node X. If node X isn't present it returns -1.
Expected Time Complexity: O(V + E)
Expected Auxiliary Space: O(V)
 
Constraints:
2  ≤  V  ≤  10^{4}
1  ≤  E  ≤  (N*(N-1))/2
0  ≤ u, v < V
1  ≤  X  ≤  10^{4}
Graph doesn't contain multiple edges and self loops.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Graph algorithms

Graph traversal

Starter code: #User function Template for python3



class Solution:

    

    #Function to find the level of node X.

    def nodeLevel(self, V, adj, X):

        # code here

Solutions:
import queue

class Solution:

	def nodeLevel(self, v, adjList, x):
		vis = [-1] * v
		s = queue.Queue()
		src = 0
		count = 0
		s.put([count, src])
		while not s.empty():
			(count, node) = s.get()
			if node == x:
				return count
			for i in adjList[node]:
				if i == x:
					return count + 1
				if vis[i] == -1:
					s.put([count + 1, i])
					vis[i] = 1
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		visit = [0] * V
		q = deque()
		q.append((0, 0))
		while q:
			(node, level) = q.popleft()
			visit[node] = 1
			if X == node:
				return level
			for i in adj[node]:
				if not visit[i]:
					q.append((i, level + 1))
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		visited = [False] * len(adj)
		level = [0] * len(adj)
		visited[0] = True
		queue = deque([0])
		while queue:
			node = queue.popleft()
			if node == X:
				return level[node]
			for n in adj[node]:
				if not visited[n]:
					visited[n] = True
					queue.append(n)
					level[n] = level[node] + 1
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		visited = [False for _ in range(V)]
		queue = deque()
		queue.append([0])
		cnt = -1
		while queue:
			n = queue.popleft()
			cnt += 1
			temp = []
			while n:
				node = n.pop(0)
				if node == X:
					return cnt
				if visited[node] == False:
					visited[node] = True
					for u in adj[node]:
						temp.append(u)
			if len(temp) != 0:
				queue.append(temp)
				del temp
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		que = deque([(0, 0)])
		visited = [0] * V
		while que:
			(node, lvl) = que.popleft()
			visited[node] = 1
			if node == X:
				return lvl
			for adjNode in adj[node]:
				if not visited[adjNode]:
					que.append((adjNode, lvl + 1))
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		q = [[0, 0]]
		(pos, len1) = (0, 1)
		visited = set()
		while pos < len1:
			(top, level) = q[pos]
			visited.add(top)
			for i in adj[top]:
				if i == X:
					return level + 1
				elif i not in visited:
					q.append([i, level + 1])
					len1 += 1
			pos += 1
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		q = deque()
		vis = [False] * len(adj)
		vis[0] = True
		q.append(0)
		lvl = 0
		while q:
			n = len(q)
			for i in range(n):
				x = q.popleft()
				for j in adj[x]:
					if j == X:
						return lvl + 1
					if vis[j] == False:
						q.append(j)
						vis[j] = True
			lvl += 1
		return -1


from queue import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		q = deque()
		q.append([0, 0])
		visited = [False] * V
		visited[0] = True
		while q:
			node = q.popleft()
			for i in adj[node[0]]:
				if i == X:
					return node[1] + 1
				if visited[i] == False:
					visited[i] = True
					q.append([i, node[1] + 1])
		return -1


from queue import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		if X == 0:
			return 0
		queue = deque()
		queue.append([0, 0])
		v = set()
		v.add(0)
		levelCount = 0
		while queue:
			node = queue.popleft()
			if node[0] == X:
				return node[1]
			levelCount = node[1] + 1
			for i in adj[node[0]]:
				if i not in v:
					queue.append([i, levelCount])
					v.add(i)
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		q = [0]
		level = 0
		vis = [0] * len(adj)
		vis[0] = 1
		while q:
			for _ in range(len(q)):
				node = q.pop(0)
				if node == X:
					return level
				for i in adj[node]:
					if not vis[i]:
						q.append(i)
						vis[i] = 1
			level += 1
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		q = deque()
		res = 0
		q.append(0)
		visit = set()
		res = 0
		while q:
			for _ in range(len(q)):
				if q:
					node = q.popleft()
				if node == X:
					return res
				for nei in adj[node]:
					if nei not in visit:
						q.append(nei)
						visit.add(nei)
			res += 1
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		s = [0, None]
		l = [[]]
		k = set()
		k.add(0)
		while len(s) != 1:
			e = s.pop(0)
			if e == None:
				l.append([])
				s.append(None)
				continue
			if e == X:
				return len(l) - 1
			for i in adj[e]:
				if i not in k:
					k.add(i)
					s.append(i)
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		if X >= V:
			return -1
		q = deque()
		q.append(0)
		l = [-1 for i in range(V)]
		l[0] = 0
		while q:
			u = q.popleft()
			for i in adj[u]:
				if l[i] == -1:
					q.append(i)
					l[i] = l[u] + 1
		return l[X]


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		if X >= V:
			return -1
		visited = [0] * V
		queue = deque()
		queue.append((0, 0))
		while queue:
			(node, count) = queue.popleft()
			if visited[node]:
				continue
			visited[node] = 1
			if node == X:
				return count
			for item in adj[node]:
				queue.append((item, count + 1))
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		if X >= V:
			return -1
		visited = [False for u in range(V)]
		q = deque()
		q.append([0, 0])
		visited[0] = True
		while q:
			(u, level) = q.popleft()
			if u == X:
				return level
			for v in adj[u]:
				if not visited[v]:
					visited[v] = True
					q.append([v, level + 1])
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		vis = [0] * V
		vis[0] = 1
		queue = [0]
		c = 0
		while queue:
			t = []
			for i in range(len(queue)):
				curr = queue.pop(0)
				t.append(curr)
				for j in adj[curr]:
					if vis[j] != 1:
						vis[j] = 1
						queue.append(j)
						t.append(j)
			c += 1
			if X in t:
				return c
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		visited = [False] * V
		level = [0] * V
		visited[0] = True
		q = deque()
		q.append(0)
		while len(q) > 0:
			value = q.popleft()
			for neighb in adj[value]:
				if visited[neighb] == False:
					level[neighb] = level[value] + 1
					visited[neighb] = True
					q.append(neighb)
				if neighb == X:
					return level[neighb]
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		Q = deque([[0, 0]])
		visit = [False] * V
		while Q:
			(u, level) = Q.popleft()
			if u == X:
				return level
			if visit[u]:
				continue
			visit[u] = True
			for v in adj[u]:
				if visit[v] == False:
					Q.append([v, level + 1])
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		visited = [0 for i in range(V + 1)]
		if X > V:
			return -1
		cur_lvl = 0
		levels = [[0]]
		while visited.index(0) < V:
			cur_nodes = levels[cur_lvl]
			nxt_lvl = []
			for i in cur_nodes:
				visited[i] = 1
				for nxt in adj[i]:
					if not visited[nxt]:
						nxt_lvl.append(nxt)
						if nxt == X:
							return cur_lvl + 1
			levels.append(nxt_lvl)
			cur_lvl += 1
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		levels = {0: 0}
		queue = [0]
		done = {0: 0}
		pointer = 0
		while pointer < len(queue):
			for j in adj[queue[pointer]]:
				try:
					done[j]
				except:
					done[j] = 0
					queue.append(j)
					levels[j] = levels[queue[pointer]] + 1
					if j == X:
						return levels[j]
			pointer += 1
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		q = deque()
		q.append(0)
		level = 0
		visited = [False for i in range(len(adj))]
		while len(q) != 0:
			count = len(q)
			while count > 0:
				idx = q.popleft()
				visited[idx] = True
				if idx == X:
					return level
				for num in adj[idx]:
					if visited[num] == False:
						q.append(num)
				count -= 1
			level += 1
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		x = deque()
		x.append([0, 0])
		visited = [False for _ in range(V)]
		visited[0] = True
		while x:
			(node, level) = x.popleft()
			if node == X:
				return level
			for y in adj[node]:
				if not visited[y]:
					visited[y] = True
					x.append([y, level + 1])
		return -1


import collections

class Solution:

	def nodeLevel(self, V, adj, X):
		lvl = 0
		q = collections.deque([0])
		visited = set()
		visited.add(0)
		while q:
			for i in range(len(q)):
				node = q.popleft()
				if node == X:
					return lvl
				for edg in adj[node]:
					if edg not in visited:
						visited.add(edg)
						q.append(edg)
			lvl += 1
		return -1


from typing import *
from collections import deque

class Solution:

	def nodeLevel(self, V: int, adj: List[List[int]], X: int):
		visited = [False] * V
		q = deque()
		visited[0] = True
		q.append(0)
		level = -1
		while len(q) > 0:
			sz = len(q)
			level += 1
			for i in range(sz):
				source = q.popleft()
				if source == X:
					return level
				for neigh in adj[source]:
					if not visited[neigh]:
						q.append(neigh)
						visited[neigh] = True
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		stack = deque()
		stack.append(0)
		level = {0: 0}
		visited = set()
		visited.add(0)
		while stack:
			n = len(stack)
			while n:
				top = stack.popleft()
				for data in adj[top]:
					if data not in visited:
						visited.add(data)
						level[data] = level[top] + 1
						stack.append(data)
				n -= 1
		if X in level:
			return level[X]
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		stack = [0]
		level = {0: 0}
		visited = set()
		visited.add(0)
		while stack:
			n = len(stack)
			while n:
				top = stack.pop(0)
				for data in adj[top]:
					if data not in visited:
						visited.add(data)
						level[data] = level[top] + 1
						stack.append(data)
				n -= 1
		if X in level:
			return level[X]
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		q = deque([0])
		steps = 0
		v = set()
		while q:
			sz = len(q)
			for _ in range(sz):
				n = q.popleft()
				v.add(n)
				if n == X:
					return steps
				for nei in adj[n]:
					if nei not in v:
						q.append(nei)
			steps += 1
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		q = [0]
		p = 0
		l = 0
		s = 1
		visited = [False for i in range(V)]
		visited[0] = True
		while p < len(q):
			node = q[p]
			if node == X:
				return l
			p += 1
			s -= 1
			for i in adj[node]:
				if visited[i] != True:
					q.append(i)
					visited[i] = True
			if s == 0:
				l += 1
				s = len(q) - p
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		visited = V * [False]
		queue = [(0, 0)]
		visited[0] = True
		for (v, level) in queue:
			if v == X:
				return level
			for neighb in adj[v]:
				if not visited[neighb]:
					visited[neighb] = True
					queue.append((neighb, level + 1))
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		level = 0
		stack = [0]
		visited = [False] * V
		while stack:
			n = len(stack)
			for i in range(n):
				node = stack.pop(0)
				if node == X:
					return level
				if visited[node] == False:
					stack.extend(adj[node])
					visited[node] = True
			level += 1
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		if X >= V:
			return -1
		level = [-1] * V
		level[0] = 0
		visited = [0] * V
		que = deque()
		que.append(0)
		visited[0] = True
		while que:
			x = que.popleft()
			for i in adj[x]:
				if not visited[i]:
					que.append(i)
					visited[i] = True
					level[i] = level[x] + 1
		return level[X]


class Solution:

	def nodeLevel(self, n, adj, X):
		queue = [0]
		level = 0
		ptr = 0
		visited = [False for i in range(n)]
		while ptr < len(queue):
			size = len(queue) - ptr
			for _ in range(size):
				visited[queue[ptr]] = True
				if queue[ptr] == X:
					return level
				for i in adj[queue[ptr]]:
					if not visited[i]:
						queue.append(i)
				ptr += 1
			level += 1
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		from queue import Queue
		vis = [False for i in range(V)]
		q = Queue()
		q.put([0, 0])
		while q.empty() == False:
			cur = q.get()
			ele = cur[0]
			lvl = cur[1]
			if vis[ele] == False:
				vis[ele] = True
				if ele == X:
					return lvl
				for i in adj[ele]:
					q.put([i, lvl + 1])
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		visited = set()
		queue = list()
		visited.add(0)
		queue.append(0)
		d = dict()
		c = 0
		d[0] = 0
		while queue:
			s = queue.pop(0)
			for i in adj[s]:
				if i not in visited:
					visited.add(i)
					queue.append(i)
					d[i] = d[s] + 1
		if X not in d.keys():
			return -1
		else:
			return d[X]


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		q = deque()
		q.append((0, 0))
		visited = [False] * V
		while q:
			c = q.popleft()
			neighs = adj[c[0]]
			for n in neighs:
				if not visited[n]:
					q.append((n, c[1] + 1))
					visited[n] = True
				if n == X:
					return c[1] + 1
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		visited = [0] * V
		queue = [0]
		level = 0
		while queue:
			curr_length = len(queue)
			while curr_length > 0:
				curr_node = queue.pop(0)
				if curr_node == X:
					return level
				if visited[curr_node] == 0:
					visited[curr_node] = 1
					for next_node in adj[curr_node]:
						if visited[next_node] == 0:
							queue.append(next_node)
				curr_length -= 1
			level += 1
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		if X == 0:
			return 0
		vis = [0] * V
		vis[0] = 1
		q = deque()
		q.append((0, 0))
		while len(q) > 0:
			p = q[0]
			q.popleft()
			curr = p[0]
			level = p[1]
			for i in range(0, len(adj[curr])):
				if vis[adj[curr][i]] == 0:
					if adj[curr][i] == X:
						return level + 1
					vis[adj[curr][i]] = 1
					q.append((adj[curr][i], level + 1))
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		q = deque()
		vis = [False] * V
		vis[0] = True
		q.append(0)
		level = 0
		while q:
			size = len(q)
			level += 1
			for i in range(size):
				node = q.popleft()
				for v in adj[node]:
					if vis[v] == False:
						if v == X:
							return level
						vis[v] = True
						q.append(v)
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		visited = [0 for i in range(V)]
		queue = deque()
		queue.append([0, 0])
		visited[0] = 1
		while queue:
			(node, level) = queue.popleft()
			if X == node:
				return level
			for neigh in adj[node]:
				if visited[neigh] == 0:
					queue.append([neigh, level + 1])
					visited[neigh] = 1
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		q = deque([(0, [0])])
		vis = set()
		vis.add(0)
		output = []
		while q:
			(node, path) = q.popleft()
			if node == X:
				return len(path) - 1
			for adjnode in adj[node]:
				if adjnode not in vis:
					vis.add(adjnode)
					q.append((adjnode, path + [adjnode]))
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		vis = [0] * V
		q = [[0, 0]]
		vis[0] = 1
		while q:
			(x, y) = q.pop(0)
			if x == X:
				return y
			for i in adj[x]:
				if vis[i] == 0:
					vis[i] = 1
					q.append([i, y + 1])
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		q = []
		visited = [False] * V
		q.append([0, 0])
		visited[0] = True
		while q:
			(u, level) = q.pop(0)
			if u == X:
				return level
			for v in adj[u]:
				if not visited[v]:
					q.append([v, level + 1])
					visited[v] = True
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		queue = [0]
		visited = [0] * V
		visited[0] = 1
		level = 0
		while queue:
			size = len(queue)
			for i in range(size):
				node = queue.pop(0)
				if node == X:
					return level
				for it in adj[node]:
					if visited[it] == 0:
						queue.append(it)
						visited[it] = 1
			level += 1
		return -1


import collections

class Solution:

	def nodeLevel(self, V, adj, X):
		g = {}
		for i in range(len(adj)):
			g[i] = adj[i]
		if len(adj) == 0 or X >= V:
			return -1
		(level, count) = (0, 0)
		queue = collections.deque([0])
		visited = dict()
		visited[0] = 1
		while len(queue) > 0:
			count = len(queue)
			for i in range(count):
				node = queue.popleft()
				visited[node] = 1
				if node == X:
					return level
				for v in adj[node]:
					if v not in visited:
						queue.append(v)
			level += 1
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		visited = set()

		def bfs(node):
			q = []
			q.append([node, 0])
			while q:
				(node, level) = q.pop(0)
				if node == X:
					return level
				visited.add(node)
				for v in adj[node]:
					if v not in visited:
						q.append([v, level + 1])
			return -1
		return bfs(0)


class Solution:

	def nodeLevel(self, V, adj, X):
		q = []
		visited = [False] * V
		q.append(0)
		visited[0] = True
		level = [0] * V
		tmp = 0
		while len(q) != 0:
			node = q.pop(0)
			if node == X:
				return level[node]
			for i in adj[node]:
				if visited[i] == False:
					q.append(i)
					visited[i] = True
					level[i] = level[node] + 1
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		visited = [False for i in range(V)]
		for i in range(V):
			if visited[i] == False:
				temp = self.bfs(i, adj, X, visited, V)
				if temp != None:
					return temp
		return -1

	def bfs(self, initial, adj, X, visited, V):
		myQ = deque()
		(i, level) = (initial, 0)
		myQ.append([i, level])
		visited[i] = True
		while myQ:
			(i, level) = myQ.popleft()
			if i == X:
				return level
			for nbr in adj[i]:
				if visited[nbr] == False:
					myQ.append([nbr, level + 1])
					visited[i] = True
		return None


class Solution:

	def nodeLevel(self, V, adj, X):
		visited = [False] * V
		queue = []
		visited[0] = True
		queue.append([0, 0])
		while queue:
			temp = queue.pop(0)
			node = temp[0]
			level = temp[1]
			if node == X:
				return level
			for i in adj[node]:
				if visited[i] == False:
					visited[i] = True
					queue.append([i, level + 1])
		return -1


from math import inf

class Solution:

	def nodeLevel(self, V, adj, X):
		level = 0
		visited = set()
		visited.add(0)
		q = [0]
		while q:
			for i in range(len(q)):
				cur = q.pop(0)
				if cur == X:
					return level
				for v in adj[cur]:
					if v not in visited:
						q.append(v)
						visited.add(v)
			level += 1
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		vis = [0] * V
		q = [[0, 0]]
		c = 0
		while c != len(q):
			t = q[c][0]
			vis[t] = 1
			if t == X:
				return q[c][1]
			for i in adj[t]:
				if vis[i] == 0:
					q.append([i, q[c][1] + 1])
			c += 1
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		level = {0: 0}
		parent = {0: None}
		nextLevel = 1
		queue = [0]
		while queue:
			for _ in range(len(queue)):
				node = queue.pop(0)
				if node == X:
					return level[node]
				for neighbor in adj[node]:
					if neighbor not in level:
						level[neighbor] = nextLevel
						parent[neighbor] = node
						queue.append(neighbor)
			nextLevel += 1
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		visited = [False] * V
		D = deque()
		D.append([0, 0])
		while D:
			(p, level) = D.popleft()
			if p == X:
				return level
			for i in adj[p]:
				if visited[i] == False:
					visited[i] = True
					D.append([i, level + 1])
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		q = [[0, 0]]
		vis = [0] * V
		while q:
			l = len(q)
			for i in range(l):
				x = q.pop(0)
				elem = x[0]
				level = x[1]
				if elem == X:
					return level
				for i in adj[elem]:
					if vis[i] != 1:
						q.append([i, level + 1])
						vis[i] = 1
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		level = [0] * V
		visited = [False] * V
		queue = []
		queue.append(0)
		visited[0] = True
		while queue:
			x = queue.pop(0)
			for j in adj[x]:
				if visited[j] == False:
					level[j] = level[x] + 1
					visited[j] = True
					queue.append(j)
		if X > V - 1:
			return -1
		return level[X]


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		visit = [False for i in range(V)]
		q = deque()
		q.append(0)
		level = -1
		while q:
			level += 1
			count = len(q)
			while count > 0:
				a = q.popleft()
				if a == X:
					return level
				visit[a] = True
				for i in adj[a]:
					if not visit[i]:
						q.append(i)
				count -= 1
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		res = [(0, 0)]
		index = 0
		visited = {0: True}
		if X == 0:
			return 0
		while index < len(res):
			node = res[index][0]
			level = res[index][1]
			for adj_node in adj[node]:
				if adj_node not in visited:
					visited[adj_node] = True
					if adj_node == X:
						return level + 1
					res.append((adj_node, level + 1))
			index += 1
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		(q, visited) = (deque([(0, 0)]), [False] * V)
		while q:
			(v, lvl) = q.popleft()
			for nei in adj[v]:
				if visited[nei]:
					continue
				if nei == X:
					return lvl + 1
				visited[nei] = True
				q.append((nei, lvl + 1))
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		visited = [False] * V
		q = [0]
		visited[0] = True
		level = -1
		while q:
			levelLen = len(q)
			level += 1
			for i in range(levelLen):
				curr = q.pop(0)
				if curr == X:
					return level
				for ngbr in adj[curr]:
					if not visited[ngbr]:
						q.append(ngbr)
						visited[ngbr] = True
		return -1


from queue import Queue

class Solution:

	def bfs(self, adj, X, V):
		levels = [0 for i in range(V)]
		visited = [False for i in range(V)]
		queue = Queue()
		queue.put(0)
		visited[0] = True
		while queue.empty() == False:
			s = queue.get()
			if s == X:
				return levels[s]
			for n in adj[s]:
				if visited[n] == False:
					levels[n] = levels[s] + 1
					visited[n] = True
					queue.put(n)
		return -1

	def nodeLevel(self, V, adj, X):
		return self.bfs(adj, X, V)


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		visited = set()
		q = deque()
		q.append(0)
		visited.add(0)
		list1 = [0 for i in range(V)]
		list1[0] = 0
		while len(q) > 0:
			value = q.popleft()
			for neighbour in adj[value]:
				if neighbour not in visited:
					list1[neighbour] = list1[value] + 1
					visited.add(neighbour)
					q.append(neighbour)
				if neighbour == X:
					return list1[neighbour]
		return -1


class Solution:

	def nodeLevel(self, n, x, R):
		q = [(0, 0)]
		v = {(0, 0)}
		while q:
			(i, k) = q.pop(0)
			if i == R:
				return k
			for j in x[i]:
				if j not in v:
					v.add(j)
					q.append((j, k + 1))
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, n, x, R):
		q = deque([(0, 0)])
		v = {(0, 0)}
		while q:
			(i, k) = q.popleft()
			if i == R:
				return k
			for j in x[i]:
				if j not in v:
					v.add(j)
					q.append((j, k + 1))
		return -1


class Solution:

	def nodeLevel(self, V, adj, x):
		if x == 0:
			return 0
		visited = [False] * V
		q = [0]
		count = 0
		while len(q) != 0:
			c = len(q)
			for i in range(c):
				pop = q.pop(0)
				if pop == x:
					return count
				for j in adj[pop]:
					if visited[j] == False:
						visited[j] = True
						q.append(j)
			count += 1
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):

		def bfs(node):
			q = [node]
			visited = set()
			visited.add(node)
			level = -1
			while q:
				level += 1
				l = len(q)
				for i in range(l):
					n = q.pop(0)
					if n == X:
						return level
					for neighbor in adj[n]:
						if neighbor not in visited:
							visited.add(neighbor)
							q.append(neighbor)
			return -1
		return bfs(0)


class Solution:

	def nodeLevel(self, V, adj, X):
		if X == 0:
			return 0
		queue = []
		visited = [0] * V
		queue.append(0)
		visited[0] = 1
		level = 0
		while queue != []:
			curr_level = [] + queue
			queue = []
			if X in curr_level:
				return level
			else:
				level += 1
			for node in curr_level:
				for neighbour in adj[node]:
					if visited[neighbour] == 0:
						queue.append(neighbour)
						visited[neighbour] = 1
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		lst = [(0, 0)]
		visited = {}
		mx_level = float('-inf')
		while len(lst):
			cur = lst.pop(0)
			node = cur[0]
			level = cur[1]
			if node == X:
				return level
			mx_level = max(mx_level, level)
			visited[node] = True
			for i in adj[node]:
				if i not in visited:
					lst.append((i, level + 1))
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		q = []
		level = 0
		visit = [False] * V
		q.append(0)
		if X == 0:
			return 0
		while q:
			n = len(q)
			level += 1
			for i in range(n):
				cur = q.pop(0)
				for j in adj[cur]:
					if j == X:
						return level
					if not visit[j]:
						q.append(j)
						visit[j] = True
		return -1


class Solution:

	def nodeLevel(self, V, adj, X):
		level = [-1] * V
		visited = set()
		q = []
		q.append(0)
		visited.add(0)
		level[0] = 0
		while q:
			x = q.pop(0)
			for i in adj[x]:
				if i not in visited:
					q.append(i)
					level[i] = level[x] + 1
					visited.add(i)
				if i == X:
					return level[X]
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		q = deque()
		q.append(0)
		visited = set()
		visited.add(0)
		level = 0
		while q:
			l = len(q)
			for _ in range(l):
				node = q.popleft()
				if node == X:
					return level
				for neigh in adj[node]:
					if neigh not in visited:
						q.append(neigh)
						visited.add(neigh)
			if len(q) != 0:
				level += 1
		return -1


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		visited = [False] * V
		visited[0] = True
		level = [0] * V
		queue = deque()
		queue.append(0)
		while queue:
			x = queue.popleft()
			for node in adj[x]:
				if not visited[node]:
					visited[node] = True
					queue.append(node)
					level[node] = level[x] + 1
		return level[X] if X in range(V) else -1
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		(V, E) = list(map(int, input().strip().split()))
		adj = [[] for i in range(V)]
		for i in range(E):
			(a, b) = map(int, input().strip().split())
			adj[a].append(b)
			adj[b].append(a)
		X = int(input())
		ob = Solution()
		print(ob.nodeLevel(V, adj, X))


class Solution:

	def nodeLevel(self, V, adj, X):
		vis = [False] * V
		level = 0
		vis[0] = True
		queue = []
		queue.append(0)
		while queue:
			size = len(queue)
			flag = 0
			while size > 0:
				u = queue.pop(0)
				for nei in adj[u]:
					if vis[nei] == False:
						vis[nei] = True
						if flag == 0:
							level += 1
							flag = 1
						queue.append(nei)
					if X == nei:
						return level
				size -= 1
		return -1
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		(V, E) = list(map(int, input().strip().split()))
		adj = [[] for i in range(V)]
		for i in range(E):
			(a, b) = map(int, input().strip().split())
			adj[a].append(b)
			adj[b].append(a)
		X = int(input())
		ob = Solution()
		print(ob.nodeLevel(V, adj, X))


class Solution:

	def nodeLevel(self, V, adj, X):
		q = [[0, 0]]
		v = set()
		while q:
			(node, lev) = q.pop(0)
			if node == X:
				return lev
			v.add(node)
			for i in adj[node]:
				if i not in v:
					q.append([i, lev + 1])
		return -1
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		(V, E) = list(map(int, input().strip().split()))
		adj = [[] for i in range(V)]
		for i in range(E):
			(a, b) = map(int, input().strip().split())
			adj[a].append(b)
			adj[b].append(a)
		X = int(input())
		ob = Solution()
		print(ob.nodeLevel(V, adj, X))


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		q = deque()
		vis = [False] * len(adj)
		vis[0] = True
		q.append(0)
		lvl = 0
		while q:
			n = len(q)
			for i in range(n):
				x = q.popleft()
				for j in adj[x]:
					if j == X:
						return lvl + 1
					if vis[j] == False:
						q.append(j)
						vis[j] = True
			lvl += 1
		return -1
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		(V, E) = list(map(int, input().strip().split()))
		adj = [[] for i in range(V)]
		for i in range(E):
			(a, b) = map(int, input().strip().split())
			adj[a].append(b)
			adj[b].append(a)
		X = int(input())
		ob = Solution()
		print(ob.nodeLevel(V, adj, X))


class Solution:

	def BFS(self, adj, V, X, dist, src, ind):
		q = []
		q.append(src)
		dist[src] = 0
		while len(q) != 0:
			u = q.pop(0)
			for v in adj[u]:
				if dist[v] == -1:
					q.append(v)
					dist[v] = dist[u] + 1
		return dist[X]

	def nodeLevel(self, V, adj, X):
		dist = [-1] * (V + 1)
		for i in range(V):
			if dist[i] == -1:
				return self.BFS(adj, V, X, dist, i, 0)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		(V, E) = list(map(int, input().strip().split()))
		adj = [[] for i in range(V)]
		for i in range(E):
			(a, b) = map(int, input().strip().split())
			adj[a].append(b)
			adj[b].append(a)
		X = int(input())
		ob = Solution()
		print(ob.nodeLevel(V, adj, X))


import collections

class Solution:

	def nodeLevel(self, V, adj, X):
		visited = [False] * V
		q = collections.deque()
		q.append(0)
		level = [None] * V
		level[0] = 0
		while q:
			node = q.popleft()
			for it in adj[node]:
				if not visited[it]:
					q.append(it)
					visited[it] = True
					level[it] = level[node] + 1
		ans = [level[idx] for idx in range(V) if idx == X]
		return ans[0] if ans else -1
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		(V, E) = list(map(int, input().strip().split()))
		adj = [[] for i in range(V)]
		for i in range(E):
			(a, b) = map(int, input().strip().split())
			adj[a].append(b)
			adj[b].append(a)
		X = int(input())
		ob = Solution()
		print(ob.nodeLevel(V, adj, X))


from collections import deque

class Solution:

	def nodeLevel(self, V, adj, X):
		vis = [False for i in range(V)]
		que = deque()
		que.append((0, 0))
		while que:
			(u, lvl) = que.popleft()
			vis[u] = True
			if u == X:
				return lvl
			for i in adj[u]:
				if not vis[i]:
					que.append((i, lvl + 1))
		return -1