You are given an Undirected Graph having unit weight, Find the shortest path from src to all the vertex and if it is unreachable to reach any vertex, then return -1 for that vertex.
Example:
Input:
n = 9, m= 10
edges=[[0,1],[0,3],[3,4],[4 ,5]
,[5, 6],[1,2],[2,6],[6,7],[7,8],[6,8]] 
src=0
Output:
0 1 2 1 2 3 3 4 4
Your Task:
You don't need to print or input anything. Complete the function shortest path() which takes a 2d vector or array edges representing the edges of undirected graph with unit weight, an integer N as number nodes, an integer M as number of edges and an integer src as the input parameters and returns an integer array or vector, denoting the vector of distance from src to all nodes.
Constraint:
1<=n,m<=100
1<=adj[i][j]<=100
Expected Time Complexity: O(N + E), where N is the number of nodes and E is edges
Expected Space Complexity: O(N)

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def shortestPath(self, edges, n, m, src):

        # code here

Solutions:
from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for _ in range(n)]
		for edge in edges:
			adj[edge[0]].append(edge[1])
			adj[edge[1]].append(edge[0])
		q = deque()
		dist = [float('inf')] * n
		q.append(src)
		dist[src] = 0
		while len(q):
			top = q.popleft()
			for neigh in adj[top]:
				if dist[neigh] > dist[top] + 1:
					dist[neigh] = dist[top] + 1
					q.append(neigh)
		for i in range(n):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


from queue import deque
import math

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for i in range(n)]
		for edge in edges:
			adj[edge[0]].append(edge[1])
			adj[edge[1]].append(edge[0])
		dist = [-1] * n
		dist[src] = 0
		q = deque()
		q.append((src, 0))
		vis = set()
		vis.add(src)
		while q:
			(node, steps) = q.popleft()
			dist[node] = steps
			for x in adj[node]:
				if x not in vis:
					vis.add(x)
					q.append((x, steps + 1))
		return dist


import queue

class Solution:

	def shortestPath(self, edges, n, m, src):
		dist = [float('inf')] * n
		s = queue.Queue()
		dist[src] = 0
		s.put(src)
		adjList = {}
		for i in range(n):
			adjList[i] = []
		for i in edges:
			u = i[0]
			v = i[1]
			adjList[u].append(v)
			adjList[v].append(u)
		while not s.empty():
			cur = s.get()
			d = dist[cur]
			for i in adjList[cur]:
				if d + 1 < dist[i]:
					dist[i] = d + 1
					s.put(i)
		for i in range(n):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


from collections import defaultdict

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = defaultdict(list)
		for (source, dst) in edges:
			adj[source].append(dst)
			adj[dst].append(source)
		distance = [float('inf') for i in range(n)]
		distance[src] = 0
		queue = []
		queue.append(src)
		while queue:
			node = queue.pop(0)
			for childs in adj[node]:
				if distance[node] + 1 < distance[childs]:
					distance[childs] = 1 + distance[node]
					queue.append(childs)
		ans = [-1 for i in range(n)]
		for i in range(len(distance)):
			if distance[i] == float('inf'):
				ans[i] = -1
			else:
				ans[i] = distance[i]
		return ans


class Solution:

	def shortestPath(self, edges, n, m, src):
		graph = [[] for i in range(n)]
		for i in edges:
			graph[i[0]].append(i[1])
			graph[i[1]].append(i[0])
		dist = [-1] * n
		q = []
		visited = [False] * (n + 1)
		q.append(src)
		visited[src] = True
		dist[src] = 0
		while len(q) > 0:
			u = q.pop(0)
			for i in graph[u]:
				if visited[i] == False:
					q.append(i)
					visited[i] = True
					dist[i] = dist[u] + 1
		return dist


class Solution:

	def shortestPath(self, edges, n, m, src):
		hmap = {}
		for i in range(n):
			hmap[i] = []
		for i in range(m):
			hmap[edges[i][0]].append(edges[i][1])
			hmap[edges[i][1]].append(edges[i][0])
		dist = [2 ** 32] * n
		dist[src] = 0
		que = []
		que.append(src)
		while len(que):
			node = que.pop(0)
			for nxt in hmap[node]:
				if dist[node] + 1 < dist[nxt]:
					dist[nxt] = 1 + dist[node]
					que.append(nxt)
		for i in range(n):
			if dist[i] == 2 ** 32:
				dist[i] = -1
		return dist


from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for _ in range(n)]
		for (node, adjnode) in edges:
			adj[node].append(adjnode)
			adj[adjnode].append(node)
		distance = [float('inf')] * n
		queue = deque()
		queue.append([src, 0])
		distance[src] = 0
		while queue:
			(node, dist) = queue.popleft()
			for adjNode in adj[node]:
				if dist + 1 < distance[adjNode]:
					distance[adjNode] = dist + 1
					queue.append([adjNode, dist + 1])
		for (index, value) in enumerate(distance):
			if value == float('inf'):
				distance[index] = -1
		return distance


class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for i in range(0, n)]
		dist = [10000 for i in range(0, n)]
		queue = []
		for i in range(0, m):
			adj[edges[i][0]].append(edges[i][1])
			adj[edges[i][1]].append(edges[i][0])
		dist[src] = 0
		queue.append(src)
		while len(queue) > 0:
			node = queue.pop(0)
			for v in adj[node]:
				if dist[node] + 1 < dist[v]:
					dist[v] = 1 + dist[node]
					queue.append(v)
		for i in range(0, n):
			if dist[i] == 10000:
				dist[i] = -1
		return dist


class Solution:

	def shortestPath(self, edges, n, m, src):
		queue = {0: [src]}
		visited = []
		d = {}
		edg = {}
		for i in range(n):
			d[i] = -1
			edg[i] = []
		for i in edges:
			edg[i[0]] += [i[1]]
			edg[i[1]] += [i[0]]
		while len(queue) != 0:
			y = min(queue)
			x = queue.pop(y)
			for i in x:
				if i not in visited:
					d[i] = y
					visited += [i]
					for j in edg[i]:
						if j in visited:
							continue
						elif y + 1 in queue:
							queue[y + 1] += [j]
						else:
							queue[y + 1] = [j]
		x = list(d.values())
		return x


from collections import deque, defaultdict

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = defaultdict(list)
		for (i, j) in edges:
			adj[i].append(j)
			adj[j].append(i)
		q = deque([(src, 0)])
		dist = [float('inf')] * n
		dist[src] = 0
		while q:
			(node, steps) = q.popleft()
			for neighbour in adj[node]:
				if dist[neighbour] > 1 + steps:
					dist[neighbour] = 1 + steps
					q.append((neighbour, steps + 1))
		ans = [-1] * n
		for i in range(n):
			if dist[i] != float('inf'):
				ans[i] = dist[i]
		return ans


class Solution:

	def shortestPath(self, edges, n, m, src):
		dist = [float('inf') for _ in range(n)]
		adj = [[] for _ in range(n)]
		for x in edges:
			u = x[0]
			v = x[1]
			adj[u].append(v)
			adj[v].append(u)
		queue = [[0, src]]
		dist[src] = 0
		while len(queue) > 0:
			node = queue[0][1]
			distance = queue[0][0]
			queue.pop(0)
			for i in adj[node]:
				if 1 + distance < dist[i]:
					dist[i] = distance + 1
					queue.append([distance + 1, i])
		for i in range(n):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		dis = [999999999 for i in range(n)]
		adj = [[] for i in range(n)]
		for i in range(m):
			adj[edges[i][0]].append(edges[i][1])
			adj[edges[i][1]].append(edges[i][0])
		q = deque()
		q.append(src)
		dis[src] = 0
		while q:
			node = q.popleft()
			for it in adj[node]:
				if dis[node] + 1 < dis[it]:
					dis[it] = 1 + dis[node]
					q.append(it)
		for i in range(n):
			if dis[i] == 999999999:
				dis[i] = -1
		return dis


from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for i in range(n)]
		for it in edges:
			adj[it[0]].append(it[1])
			adj[it[1]].append(it[0])
		dist = [1000000000.0] * n
		dist[src] = 0
		q = deque()
		q.append(src)
		while len(q) != 0:
			node = q.pop()
			for it in adj[node]:
				if dist[node] + 1 < dist[it]:
					dist[it] = dist[node] + 1
					q.append(it)
		for i in range(n):
			if dist[i] == 1000000000.0:
				dist[i] = -1
		return dist


import heapq

class Solution:

	def shortestPath(self, edges, n, m, s):
		d = {}
		for i in edges:
			if i[0] not in d:
				d[i[0]] = [i[1]]
			else:
				d[i[0]].append(i[1])
			if i[1] not in d:
				d[i[1]] = [i[0]]
			else:
				d[i[1]].append(i[0])
		distance = [pow(10, 5) + 1 for _ in range(n)]
		q = [[0, s]]
		distance[s] = 0
		heapq.heapify(q)
		while len(q) != 0:
			curEle = heapq.heappop(q)
			try:
				for i in d[curEle[1]]:
					nSum = curEle[0] + 1
					if distance[i] > nSum:
						distance[i] = nSum
						heapq.heappush(q, [nSum, i])
			except:
				continue
		for i in range(n):
			if distance[i] == pow(10, 5) + 1:
				distance[i] = -1
		return distance


from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		(res, adj) = ([-1] * n, [[] for i in range(n)])
		for (a, b) in edges:
			adj[a].append(b)
			adj[b].append(a)
		res[src] = 0
		que = deque([(src, 0)])
		while que:
			(node, dis) = que.popleft()
			for adjNode in adj[node]:
				if res[adjNode] == -1 or dis + 1 < res[adjNode]:
					res[adjNode] = dis + 1
					que.append((adjNode, dis + 1))
		return res


from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		dis = [-1 for _ in range(n)]
		adj = [[] for _ in range(n)]
		for (u, v) in edges:
			adj[u].append(v)
			adj[v].append(u)
		q = deque()
		q.append([src, 0])
		while q:
			(e, d) = q.popleft()
			if dis[e] != -1:
				continue
			else:
				dis[e] = d
			for v in adj[e]:
				if dis[v] == -1:
					q.append([v, d + 1])
		return dis


class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for i in range(n)]
		for i in range(m):
			adj[edges[i][0]].append(edges[i][1])
			adj[edges[i][1]].append(edges[i][0])
		stack = []
		stack.append([src, 0])
		dist = [999999 for i in range(n)]
		dist[src] = 0
		while stack:
			s = stack.pop()
			for i in adj[s[0]]:
				if dist[i] > s[1] + 1:
					dist[i] = s[1] + 1
					stack.append([i, s[1] + 1])
		for i in range(n):
			if dist[i] == 999999:
				dist[i] = -1
		return dist


from collections import defaultdict, deque
import sys

class Solution:

	def shortestPath(self, edges, n, m, src):
		adjList = defaultdict(list)
		for edge in edges:
			adjList[edge[0]].append(edge[1])
			adjList[edge[1]].append(edge[0])
		queue = deque()
		queue.append((src, 0))
		dist = [sys.maxsize for i in range(n)]
		dist[src] = 0
		while queue:
			(node, dis) = queue.popleft()
			for edge in adjList[node]:
				if dis + 1 < dist[edge]:
					dist[edge] = dis + 1
					queue.append((edge, dist[edge]))
		for i in range(n):
			if dist[i] == sys.maxsize:
				dist[i] = -1
		return dist


from collections import defaultdict, deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		path = defaultdict(list)
		for (u, v) in edges:
			path[u].append(v)
			path[v].append(u)
		dist = [float('inf')] * n
		dist[src] = 0
		q = deque()
		q.append(src)
		while q:
			node = q.popleft()
			for i in path[node]:
				if dist[node] + 1 < dist[i]:
					dist[i] = 1 + dist[node]
					q.append(i)
		for i in range(len(dist)):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


class Solution:

	def shortestPath(self, edges, n, m, src):
		res = {}
		adj = {}
		for i in range(n):
			res[i] = float('inf')
			adj[i] = []
		res[src] = 0
		vis = set()
		for node in edges:
			adj[node[0]].append(node[1])
			adj[node[1]].append(node[0])
		from collections import deque
		q = deque()
		q.append([src, 1])
		vis.add(src)
		while q:
			(popped, dis) = q.popleft()
			for node in adj[popped]:
				if node not in vis:
					q.append([node, dis + 1])
					res[node] = dis
					vis.add(node)
		op = []
		for i in res:
			if res[i] == float('inf'):
				op.append(-1)
			else:
				op.append(res[i])
		return op


from collections import defaultdict

class Solution:

	def shortestPath(self, edges, n, m, src):
		graph = defaultdict(list)
		for i in edges:
			graph[i[0]].append(i[1])
			graph[i[1]].append(i[0])
		dist = [99999] * n
		dist[src] = 0
		queue = [src]
		while queue:
			temp = queue.pop(0)
			for adj in graph[temp]:
				if dist[temp] + 1 < dist[adj]:
					dist[adj] = dist[temp] + 1
					queue.append(adj)
		for i in range(n):
			if dist[i] == 99999:
				dist[i] = -1
		return dist


class Solution:

	def shortestPath(self, edges, n, m, src):
		q = []
		dist = [1000000000.0] * n
		dist[src] = 0
		adj = [[] for _ in range(n)]
		ans = [-1] * n
		q.append(src)
		for i in edges:
			adj[i[0]].append(i[1])
			adj[i[1]].append(i[0])
		while q:
			node = q.pop(0)
			for adjNode in adj[node]:
				if dist[node] + 1 < dist[adjNode]:
					dist[adjNode] = dist[node] + 1
					q.append(adjNode)
		for i in range(n):
			if dist[i] != 1000000000.0:
				ans[i] = dist[i]
		return ans


class Solution:

	def shortestPath(self, edges, n, m, src):
		dis = [float('inf')] * n
		vis = [0] * n
		queue = [src]
		adj_list = [[] for _ in range(n)]
		for (i, j) in edges:
			adj_list[i].append(j)
			adj_list[j].append(i)
		vis[src] = 1
		dis[src] = 0
		cnt = 0
		while queue:
			x = len(queue)
			for i in range(x):
				y = queue.pop(0)
				for adj in adj_list[y]:
					if vis[adj] == 0:
						queue.append(adj)
						vis[adj] = 1
						dis[adj] = cnt + 1
			cnt += 1
		for i in range(n):
			if vis[i] == 0:
				dis[i] = -1
		return dis


from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for _ in range(n)]
		for (a, b) in edges:
			adj[a].append(b)
			adj[b].append(a)
		sp = [float('inf')] * n
		sp[src] = 0
		q = deque([(src, 0)])
		while len(q):
			(cur, dist) = q.popleft()
			for ele in adj[cur]:
				if sp[ele] > dist + 1:
					sp[ele] = dist + 1
					q.append((ele, dist + 1))
		for i in range(n):
			if sp[i] == float('inf'):
				sp[i] = -1
		return sp


import math

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for i in range(n)]
		for (u, v) in edges:
			adj[u].append(v)
			adj[v].append(u)
		dist = [math.inf] * n
		dist[src] = 0
		q = []
		q.append(src)
		while q:
			s = q.pop(0)
			for v in adj[s]:
				if dist[s] + 1 < dist[v]:
					dist[v] = 1 + dist[s]
					q.append(v)
		ans = [-1] * n
		for i in range(n):
			if dist[i] != math.inf:
				ans[i] = dist[i]
		return ans


from collections import deque
from typing import List

class Solution:

	def shortestPath(self, edges: List[List[int]], N: int, M: int, src: int) -> List[int]:
		adj = [[] for _ in range(N)]
		for (u, v) in edges:
			adj[u].append(v)
			adj[v].append(u)
		dist = [float('inf') for _ in range(N)]
		dist[src] = 0
		q = deque([src])
		while q:
			node = q.popleft()
			for neighbor in adj[node]:
				if dist[node] + 1 < dist[neighbor]:
					dist[neighbor] = dist[node] + 1
					q.append(neighbor)
		ans = [-1 if d == float('inf') else d for d in dist]
		return ans


from queue import Queue

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for i in range(n)]
		for (a, b) in edges:
			adj[a].append(b)
			adj[b].append(a)
		dis = [float('inf')] * n
		q = Queue()
		q.put(src)
		dis[src] = 0
		cnt = 1
		while not q.empty():
			nn = q.qsize()
			for i in range(nn):
				node = q.get()
				for child in adj[node]:
					if cnt < dis[child]:
						dis[child] = cnt
						q.put(child)
			cnt += 1
		for i in range(len(dis)):
			if dis[i] == float('inf'):
				dis[i] = -1
		return dis


from collections import defaultdict

class Solution:

	def shortestPath(self, edges, n, m, src):
		graph = defaultdict(list)
		for (u, v) in edges:
			graph[u].append(v)
			graph[v].append(u)
		queue = [(src, 0)]
		dist_arr = [float('inf')] * n
		dist_arr[src] = 0
		while queue:
			(node, dist) = queue.pop(0)
			for v in graph[node]:
				cur_dist = dist + 1
				if dist_arr[v] > cur_dist:
					queue.append((v, cur_dist))
					dist_arr[v] = cur_dist
		dist_arr = [-1 if i == float('inf') else i for i in dist_arr]
		return dist_arr


from collections import deque
from collections import defaultdict
import math

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = defaultdict(list)
		for (u, v) in edges:
			adj[u].append(v)
			adj[v].append(u)
		dis = [math.inf] * n
		q = deque()
		q.append([src, 0])
		dis[src] = 0
		while q:
			node = q.popleft()
			u = node[0]
			distance = node[1]
			for i in adj[u]:
				if dis[i] > 1 + distance:
					dis[i] = 1 + distance
					q.append([i, dis[i]])
		for i in range(n):
			if dis[i] == math.inf:
				dis[i] = -1
		return dis


from collections import defaultdict, deque
import math

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = defaultdict(list)
		for (u, v) in edges:
			adj[u].append(v)
			adj[v].append(u)
		visited = [0] * n
		q = deque()
		dist = [math.inf] * n
		dist[src] = 0
		q.append(src)
		while q:
			s = q.popleft()
			for u in adj[s]:
				if dist[s] + 1 < dist[u]:
					dist[u] = dist[s] + 1
					q.append(u)
		for i in range(n):
			if dist[i] == math.inf:
				dist[i] = -1
		return dist


from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] * m for _ in range(n)]
		for i in edges:
			adj[i[0]].append(i[1])
			adj[i[1]].append(i[0])
		dis = [float('inf')] * n
		q = deque()
		q.append((src, 0))
		dis[src] = 0
		while q:
			(node, d) = q.popleft()
			for i in adj[node]:
				if d + 1 < dis[i]:
					dis[i] = d + 1
					q.append((i, d + 1))
		for i in range(n):
			if dis[i] == float('inf'):
				dis[i] = -1
		return dis


from collections import deque, defaultdict

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = defaultdict(list)
		for (u, v) in edges:
			adj[u].append(v)
			adj[v].append(u)
		dist = [float('inf') for _ in range(n)]
		queue = deque()
		queue.append((src, 0))
		dist[src] = 0
		while queue:
			(u, d) = queue.popleft()
			for v in adj[u]:
				if dist[v] > d + 1:
					dist[v] = d + 1
					queue.append((v, d + 1))
		for i in range(n):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		grph = [[] for i in range(n)]
		for edge in edges:
			x = edge[0]
			y = edge[1]
			grph[x].append(y)
			grph[y].append(x)
		ans = [99999] * n
		q = deque()
		ans[src] = 0
		q.append([src, 0])
		vis = set()
		vis.add(src)
		while q:
			(p, dist) = q.pop()
			for el in grph[p]:
				if el in vis:
					continue
				if ans[el] > dist + 1:
					ans[el] = dist + 1
					q.appendleft([el, dist + 1])
					vis.add(el)
		for i in range(n):
			if ans[i] == 99999:
				ans[i] = -1
		return ans


class Solution:

	def shortestPath(self, edges, n, m, src):
		adjs = [[] for _ in range(n)]
		for (a, b) in edges:
			adjs[a].append(b)
			adjs[b].append(a)
		g = [-1] * n
		g[src] = 0
		(q1, q2) = ([], [src])
		d = 0
		while q2:
			(q1, q2) = (q2, q1)
			q2.clear()
			d += 1
			for u in q1:
				for v in adjs[u]:
					if g[v] == -1:
						q2.append(v)
						g[v] = d
		return g


class Solution:

	def shortestPath(self, edges, n, m, src):
		q = [src]
		adj = []
		ans = []
		visited = []
		for i in range(n):
			ans.append(99999999)
			visited.append(0)
		for i in range(n):
			adj.append([])
		for i in range(m):
			adj[edges[i][0]].append(edges[i][1])
			adj[edges[i][1]].append(edges[i][0])
		ans[src] = 0
		while len(q) != 0:
			node = q[0]
			visited[node] = 1
			q.pop(0)
			for i in adj[node]:
				if visited[i] == 0:
					visited[i] = 1
					q.append(i)
					ans[i] = min(ans[i], ans[node] + 1)
		for i in range(n):
			if ans[i] == 99999999:
				ans[i] = -1
		return ans


import sys
import heapq
import collections

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for i in range(n)]
		for (x, y) in edges:
			adj[x].append(y)
			adj[y].append(x)
		dist = [sys.maxsize for i in range(n)]
		q = collections.deque()
		q.append(src)
		dist[src] = 0
		while q:
			node = q.popleft()
			for it in adj[node]:
				if dist[node] + 1 < dist[it]:
					q.append(it)
					dist[it] = dist[node] + 1
		for i in range(n):
			if dist[i] == sys.maxsize:
				dist[i] = -1
		return dist


from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for i in range(n)]
		for i in edges:
			adj[i[0]].append(i[1])
			adj[i[1]].append(i[0])
		dist = [1000000000.0] * n
		dist[src] = 0
		q = deque()
		q.append(src)
		while q:
			node = q.popleft()
			for i in adj[node]:
				if dist[node] + 1 < dist[i]:
					dist[i] = 1 + dist[node]
					q.append(i)
		ans = [-1] * n
		for i in range(n):
			if dist[i] != 1000000000.0:
				ans[i] = dist[i]
		return ans


import collections

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj_list = dict()
		for node in range(n):
			adj_list[node] = []
		for edge in edges:
			node1 = edge[0]
			node2 = edge[1]
			adj_list[node1].append(node2)
			adj_list[node2].append(node1)
		res = [float('inf')] * n
		res[src] = 0
		q = collections.deque()
		q.append((src, 0))
		while q:
			(node, dis) = q.popleft()
			for adj in adj_list[node]:
				if res[adj] > dis + 1:
					res[adj] = dis + 1
					q.append((adj, dis + 1))
		res = [val if val != float('inf') else -1 for val in res]
		return res


from queue import Queue

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for _ in range(n)]
		for edge in edges:
			(u, v) = edge
			adj[u].append(v)
			adj[v].append(u)
		dist = [float('inf') for _ in range(n)]
		q = Queue()
		q.put(src)
		dist[src] = 0
		while not q.empty():
			node = q.get()
			for nei in adj[node]:
				if dist[nei] > 1 + dist[node]:
					dist[nei] = 1 + dist[node]
					q.put(nei)
		for i in range(n):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


import sys

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for _ in range(n)]
		for i in edges:
			adj[i[0]].append(i[1])
			adj[i[1]].append(i[0])
		distance = [sys.maxsize] * n
		distance[src] = 0
		q = [src]
		while q:
			node = q.pop(0)
			for i in adj[node]:
				if distance[node] + 1 < distance[i]:
					q.append(i)
					distance[i] = distance[node] + 1
		for i in range(len(distance)):
			if distance[i] == sys.maxsize:
				distance[i] = -1
		return distance


from collections import defaultdict

class Solution:

	def shortestPath(self, edges, n, m, src):
		maxn = int(1000000000.0)
		dist = [maxn] * n
		gph = defaultdict(list)
		for i in edges:
			gph[i[0]].append(i[1])
			gph[i[1]].append(i[0])
		q = []
		q.append(src)
		dist[src] = 0
		while len(q):
			node = q.pop(0)
			for adj in gph[node]:
				if dist[node] + 1 < dist[adj]:
					dist[adj] = 1 + dist[node]
					q.append(adj)
		ans = [-1] * n
		for i in range(n):
			if dist[i] != maxn:
				ans[i] = dist[i]
		return ans


class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for i in range(n)]
		for (i, j) in edges:
			adj[i].append(j)
			adj[j].append(i)
		q = [src]
		d = [float('inf') for i in range(n)]
		d[src] = 0
		while q:
			x = q.pop(0)
			for i in adj[x]:
				if d[x] + 1 < d[i]:
					d[i] = d[x] + 1
					q.append(i)
		for i in range(n):
			if d[i] == float('inf'):
				d[i] = -1
		return d


from math import inf

class Solution:

	def shortestPath(self, edges, n, m, src):
		q = []
		dist = [float('inf')] * n
		adj = [[] for i in range(n)]
		for i in range(m):
			v1 = edges[i][0]
			v2 = edges[i][1]
			adj[v1].append(v2)
			adj[v2].append(v1)
		dist[src] = 0
		q.append([src, 0])
		while q:
			(curr, distance) = q.pop(0)
			for i in adj[curr]:
				if distance + 1 < dist[i]:
					dist[i] = 1 + distance
					q.append([i, dist[i]])
		ans = []
		for i in dist:
			if i != float('inf'):
				ans.append(i)
			else:
				ans.append(-1)
		return ans


class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for i in range(n)]
		for edge in edges:
			u = edge[0]
			v = edge[1]
			adj[u].append(v)
			adj[v].append(u)
		maxi = 10 ** 9
		dist = [maxi for i in range(n)]
		dist[src] = 0
		queue = []
		queue.append(src)
		while len(queue) > 0:
			e = queue.pop()
			for x in adj[e]:
				if dist[e] + 1 < dist[x]:
					dist[x] = dist[e] + 1
					queue.append(x)
		for i in range(n):
			if dist[i] == maxi:
				dist[i] = -1
		return dist


class Solution:

	def shortestPath(self, edges, n, m, src):
		visited = [False for i in range(n)]
		distance = [1000000 for i in range(n)]
		adj = [[] for i in range(n)]
		for i in edges:
			if i[0] == i[1]:
				continue
			adj[i[0]].append(i[1])
			adj[i[1]].append(i[0])

		def dfs(sv):
			visited[sv] = True
			for i in adj[sv]:
				if distance[i] <= distance[sv] + 1:
					continue
				else:
					distance[i] = distance[sv] + 1
					dfs(i)
		distance[src] = 0
		dfs(src)
		for i in range(len(distance)):
			if distance[i] == 1000000:
				distance[i] = -1
		return distance


from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for _ in range(n)]
		for (v, it) in edges:
			adj[it].append(v)
			adj[v].append(it)

		def dfs(node):
			vis[node] = 1
			for item in adj[node]:
				if dist[item] > dist[node] + 1:
					dist[item] = dist[node] + 1
				if vis[item] == 0:
					dfs(item)
			vis[node] = 0
		vis = [0] * n
		dist = [float('inf')] * n
		dist[src] = 0
		for i in range(n):
			if vis[i] == 0:
				dfs(i)
		for i in range(n):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for _ in range(n)]
		for (v, item) in edges:
			adj[v].append([item, 1])
			adj[item].append([v, 1])
		q = deque()
		q.append(src)
		dist = [float('inf')] * n
		dist[src] = 0
		while q:
			v = q.popleft()
			for (item, wt) in adj[v]:
				if dist[item] > dist[v] + 1:
					dist[item] = dist[v] + 1
					q.append(item)
		for d in range(n):
			if dist[d] == float('inf'):
				dist[d] = -1
		return dist


from queue import Queue

class Solution:

	def shortestPath(self, edges, n, m, src):
		vis = [-1] * n
		adj = [[] for i in range(n)]
		for i in range(m):
			v1 = edges[i][0]
			v2 = edges[i][1]
			adj[v1].append(v2)
			adj[v2].append(v1)
		q1 = Queue()
		q1.put([src, 0])
		while q1.qsize() != 0:
			node = q1.get()
			v1 = node[0]
			dis = node[1]
			if vis[v1] == -1:
				vis[v1] = dis
			else:
				continue
			neighbours = adj[v1]
			for neigh in neighbours:
				if vis[neigh] == -1:
					q1.put([neigh, dis + 1])
		return vis


class Solution:

	def create_graph(self, edges, n):
		graph = [[] for node in range(n)]
		for edge in edges:
			graph[edge[0]].append(edge[1])
			graph[edge[1]].append(edge[0])
		return graph

	def shortestPath(self, edges, n, m, src):
		graph = self.create_graph(edges, n)
		visited = [-1 for node in range(n)]
		from queue import Queue
		import sys
		q = Queue(maxsize=0)
		q.put(src)
		ans = [-1] * n
		ans[src] = 0
		visited[src] = 1
		curr_level = 1
		while q.qsize():
			q_size = q.qsize()
			while q_size:
				curr_node = q.get()
				for nbr in graph[curr_node]:
					if visited[nbr] == -1:
						visited[nbr] = 1
						ans[nbr] = curr_level
						q.put(nbr)
				q_size = q_size - 1
			curr_level = curr_level + 1
		return ans


class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for i in range(n)]
		for i in edges:
			adj[i[0]].append(i[1])
			adj[i[1]].append(i[0])
		dist = [1000000000.0] * n
		dist[src] = 0
		st = []
		st.append(src)
		while st:
			node = st.pop()
			for i in adj[node]:
				if dist[node] + 1 < dist[i]:
					dist[i] = dist[node] + 1
					st.append(i)
		for i in range(n):
			if dist[i] == 1000000000.0:
				dist[i] = -1
		return dist


import math

class Solution:

	def shortestPath(self, edges, n, m, src):
		adjList = {}
		for (s, dest) in edges:
			adjList.setdefault(s, []).append(dest)
			adjList.setdefault(dest, []).append(s)
		out = [math.inf] * n
		out[src] = 0
		q = [[src, -1, 0]]
		while q:
			(node, prev, currDist) = q.pop(0)
			for nei in adjList.get(node, []):
				newDist = currDist + 1
				if out[nei] == math.inf or newDist < out[nei]:
					out[nei] = newDist
					q.append([nei, node, newDist])
		for (idx, ele) in enumerate(out):
			if ele == math.inf:
				out[idx] = -1
		return out


from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		adjList = [[] for i in range(n)]
		for edge in edges:
			(a, b) = edge
			adjList[a].append(b)
			adjList[b].append(a)
		vis = [False] * n
		dist = [-1] * n
		q = deque()
		q.append(src)
		dist[src] = 0
		vis[src] = True
		while len(q) > 0:
			curr = q.popleft()
			for nbr in adjList[curr]:
				if not vis[nbr]:
					dist[nbr] = dist[curr] + 1
					vis[nbr] = True
					q.append(nbr)
		return dist


from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		ad = [[] for i in range(n)]
		for i in edges:
			(a, b) = i
			ad[a].append(b)
			ad[b].append(a)
		v = [False] * n
		d = [-1] * n
		q = deque()
		q.append(src)
		d[src] = 0
		v[src] = True
		while len(q) > 0:
			c = q.popleft()
			for i in ad[c]:
				if not v[i]:
					d[i] = d[c] + 1
					v[i] = True
					q.append(i)
		return d


from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		g = [[] for _ in range(n)]
		for e in edges:
			g[e[0]].append(e[1])
			g[e[1]].append(e[0])
		dist = [-1] * n
		dist[src] = 0
		q = deque()
		q.append((src, 0))
		while len(q) > 0:
			(curr, d) = q.popleft()
			for nb in g[curr]:
				if dist[nb] == -1:
					dist[nb] = d + 1
					q.append((nb, d + 1))
		return dist


from collections import defaultdict as dict
from collections import deque as dq

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = dict(list)
		for edge in edges:
			adj[edge[0]].append(edge[1])
			adj[edge[1]].append(edge[0])
		d = [float('inf') for i in range(n)]
		d[src] = 0
		q = dq([(src, 0)])
		while q:
			(node, nodeDist) = q.pop()
			for neib in adj[node]:
				neibDist = nodeDist + 1
				if neibDist < d[neib]:
					d[neib] = neibDist
					q.append((neib, neibDist))
		for (ind, dist) in enumerate(d):
			if dist == float('inf'):
				d[ind] = -1
		return d


from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		graph = [[] for _ in range(n)]
		for (u, v) in edges:
			graph[u].append(v)
			graph[v].append(u)
		dis = [float('inf') for _ in range(n)]
		queue = deque([src])
		dis[src] = 0
		while queue:
			root = queue.popleft()
			for node in graph[root]:
				if dis[root] + 1 < dis[node]:
					dis[node] = 1 + dis[root]
					queue.append(node)
		for i in range(n):
			if dis[i] == float('inf'):
				dis[i] = -1
		return dis


class Solution:

	def shortestPath(self, edges, n, m, src):
		graph = {i: [] for i in range(n)}
		for (u, v) in edges:
			graph[u].append(v)
			graph[v].append(u)
		dist = [float('inf')] * n
		dist[src] = 0
		q = [src]
		while q:
			u = q.pop(0)
			for v in graph[u]:
				if dist[u] + 1 < dist[v]:
					dist[v] = dist[u] + 1
					q.append(v)
		for i in range(n):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


import collections

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for _ in range(n)]
		dist = [float('infinity') for _ in range(n)]
		for dt in edges:
			(u, v) = (dt[0], dt[1])
			adj[u].append(v)
			adj[v].append(u)
		deque = collections.deque()
		deque.append((0, src))
		dist[src] = 0
		while len(deque) > 0:
			for _ in range(len(deque)):
				dt = deque.popleft()
				(wt, u) = (dt[0], dt[1])
				for node in adj[u]:
					if wt + 1 < dist[node]:
						dist[node] = wt + 1
						deque.append((wt + 1, node))
		for i in range(len(dist)):
			if dist[i] == float('infinity'):
				dist[i] = -1
		return dist


from collections import deque, defaultdict

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = defaultdict(list)
		for (u, v) in edges:
			adj[u].append(v)
			adj[v].append(u)
		dist = [10000000.0] * n
		dist[src] = 0
		queue = deque()
		queue.append(src)
		while queue:
			node = queue.popleft()
			for child in adj[node]:
				if dist[node] + 1 < dist[child]:
					dist[child] = dist[node] + 1
					queue.append(child)
		for i in range(len(dist)):
			if dist[i] == 10000000.0:
				dist[i] = -1
		return dist


from collections import deque, defaultdict

class Solution:

	def shortestPath(self, edges, n, m, src):
		graph = defaultdict(list)
		for (u, v) in edges:
			graph[u].append(v)
			graph[v].append(u)
		distance = [float('inf')] * n
		distance[src] = 0
		queue = deque()
		queue.append(src)
		while queue:
			node = queue.popleft()
			for nei in graph[node]:
				if distance[node] + 1 < distance[nei]:
					distance[nei] = distance[node] + 1
					queue.append(nei)
		return [-1 if distance[i] == float('inf') else distance[i] for i in range(len(distance))]


from collections import deque, defaultdict

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = defaultdict(list)
		for v in edges:
			adj[v[0]].append(v[1])
			adj[v[1]].append(v[0])
		ans = [10000000000.0] * n
		ans[src] = 0
		q = deque()
		q.append((src, 0))
		while q:
			(temp, d) = q.popleft()
			ans[temp] = min(ans[temp], d)
			for v in adj[temp]:
				if ans[v] > d + 1:
					q.append((v, d + 1))
		for i in range(n):
			if ans[i] == 10000000000.0:
				ans[i] = -1
		return ans


from queue import Queue

class Solution:

	def shortestPath(self, edges, n, m, src):
		visited = [0 for i in range(n)]
		adj = [[] for i in range(n)]
		for edge in edges:
			adj[edge[0]].append(edge[1])
			adj[edge[1]].append(edge[0])
		q = Queue()
		dist = [1000000000.0 for i in range(n)]
		dist[src] = 0
		visited[src] = 1
		q.put(src)
		while not q.empty():
			node = q.get()
			for u in adj[node]:
				if dist[u] > dist[node] + 1:
					dist[u] = dist[node] + 1
					q.put(u)
		for i in range(n):
			if dist[i] == 1000000000.0:
				dist[i] = -1
		return dist


from collections import defaultdict
from collections import deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = defaultdict(list)
		for i in edges:
			(u, v) = i
			adj[u].append(v)
			adj[v].append(u)
		mx = float('inf')
		dist = [mx] * n
		dist[src] = 0
		q = deque()
		q.append([src, 0])
		while q:
			(ele, wt) = q.popleft()
			for it in adj[ele]:
				if dist[ele] + 1 < dist[it]:
					dist[it] = dist[ele] + 1
					q.append([it, wt + 1])
		for i in range(n):
			if dist[i] == mx:
				dist[i] = -1
		return dist


import collections
import math

class Solution:

	def shortestPath(self, edges, n, m, src):
		dist = [math.inf] * n
		dist[src] = 0
		graph = collections.defaultdict(list)
		for (u, v) in edges:
			graph[u].append(v)
			graph[v].append(u)
		q = collections.deque()
		q.append(src)
		distance = 1
		while q:
			for _ in range(len(q)):
				node = q.popleft()
				for nei in graph[node]:
					if dist[nei] > distance:
						dist[nei] = distance
						q.append(nei)
			distance += 1
		for i in range(n):
			if dist[i] == math.inf:
				dist[i] = -1
		return dist


from sys import maxsize as maxx

class Solution:

	def shortestPath(self, edges, n, m, src):
		adjL = [[] for i in range(n)]
		for i in range(len(edges)):
			adjL[edges[i][0]].append(edges[i][1])
			adjL[edges[i][1]].append(edges[i][0])
		dist = [maxx for i in range(n)]
		vis = [0 for i in range(n)]
		q = []
		q.append(src)
		dist[src] = 0
		vis[src] = 1
		while q:
			node = q.pop(0)
			d = dist[node]
			for n in adjL[node]:
				if vis[n] == 0:
					dist[n] = min(dist[n], d + 1)
					vis[n] += 1
					q.append(n)
		for i in range(len(dist)):
			if dist[i] == maxx:
				dist[i] = -1
		return dist


from collections import defaultdict

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = defaultdict(list)
		for i in edges:
			adj[i[0]].append(i[1])
			adj[i[1]].append(i[0])
		q = []
		q.append(src)
		dist = [9999999999] * n
		dist[src] = 0
		while q:
			temp = q.pop(0)
			for i in adj[temp]:
				if dist[temp] + 1 < dist[i]:
					dist[i] = dist[temp] + 1
					q.append(i)
		ans = [-1] * n
		for i in range(n):
			if dist[i] != 9999999999:
				ans[i] = dist[i]
		return ans


from collections import *
import heapq

class Solution:

	def shortestPath(self, edges, n, m, src):
		d = defaultdict(list)
		for i in edges:
			d[i[0]].append(i[1])
			d[i[1]].append(i[0])
		dist = [float('inf') for i in range(n)]
		dist[src] = 0
		queue = [[0, src]]
		while len(queue) != 0:
			(d1, t) = heapq.heappop(queue)
			for n in d[t]:
				if d1 + 1 < dist[n]:
					dist[n] = d1 + 1
					queue.append([dist[n], n])
		for i in range(len(dist)):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


from collections import deque, defaultdict

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = defaultdict(list)
		for (ni, p) in edges:
			adj[ni].append(p)
			adj[p].append(ni)
		q = deque()
		dist = [float('inf')] * n
		dist[src] = 0
		q.append(src)
		while q:
			node = q.popleft()
			for ele in adj[node]:
				if dist[node] + 1 < dist[ele]:
					dist[ele] = dist[node] + 1
					q.append(ele)
		return [-1 if i == float('inf') else i for i in dist]


class Solution:

	def shortestPath(self, edges, n, m, src):
		dist = [10 ** 9] * n
		adj = [[] for i in range(n)]
		q = []
		for i in range(m):
			adj[edges[i][0]].append(edges[i][1])
			adj[edges[i][1]].append(edges[i][0])
		q.append(src)
		dist[src] = 0
		while q:
			s = q.pop(0)
			for i in adj[s]:
				if dist[i] > dist[s] + 1:
					dist[i] = dist[s] + 1
					q.append(i)
		for i in range(n):
			if dist[i] == 10 ** 9:
				dist[i] = -1
		return dist


from collections import defaultdict, deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = defaultdict(list)
		for (a, b) in edges:
			adj[a].append(b)
			adj[b].append(a)
		q = deque()
		q.append((src, 0))
		dist = [float('inf') for i in range(n)]
		dist[src] = 0
		while q:
			(node, wt) = q.pop()
			for neigh in adj[node]:
				if dist[neigh] > dist[node] + 1:
					dist[neigh] = dist[node] + 1
					q.append((neigh, wt + 1))
		for i in range(n):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


import collections

class Solution:

	def shortestPath(self, edges, n, m, src):
		q = collections.deque()
		dist = [float('inf') for i in range(n)]
		adj = {}
		for (u, v) in edges:
			if adj.get(u) is not None:
				adj[u].append(v)
			else:
				adj[u] = [v]
			if adj.get(v) is not None:
				adj[v].append(u)
			else:
				adj[v] = [u]
		q.append((src, 0))
		dist[src] = 0
		while len(q) != 0:
			(node, dis) = q.popleft()
			if adj.get(node):
				for n in adj[node]:
					if dist[node] + 1 < dist[n]:
						dist[n] = dist[node] + 1
						q.append((n, dis + 1))
		return [i if i != float('inf') else -1 for i in dist]


from collections import defaultdict, deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for i in range(n)]
		for (u, v) in edges:
			adj[u].append(v)
			adj[v].append(u)
		dist = [float('inf')] * n
		dist[src] = 0
		q = []
		q.append([src, 0])
		while q:
			(node, weight) = q.pop(0)
			for u in adj[node]:
				mindis = min(dist[node] + 1, dist[u])
				if dist[u] > mindis:
					dist[u] = mindis
					q.append([u, dist[u]])
		for i in range(n):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


from collections import defaultdict, deque

class Solution:

	def shortestPath(self, edges, n, m, src):
		graph = defaultdict(list)
		for (u, v) in edges:
			graph[u].append(v)
			graph[v].append(u)
		weight = [float('inf')] * n
		q = deque()
		q.append((src, 0))
		while q:
			(currNode, currDistance) = q.popleft()
			if currDistance < weight[currNode]:
				weight[currNode] = currDistance
				for neiNode in graph[currNode]:
					q.append((neiNode, currDistance + 1))
		for i in range(len(weight)):
			if weight[i] == float('inf'):
				weight[i] = -1
		return weight


from collections import deque
import math

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for _ in range(n)]
		for i in edges:
			adj[i[0]].append(i[1])
			adj[i[1]].append(i[0])
		q = deque()
		dist = [math.inf] * n
		dist[src] = 0
		q.append([src, 0])
		while len(q) != 0:
			a = q.popleft()
			for i in adj[a[0]]:
				if dist[i] > a[1] + 1:
					dist[i] = a[1] + 1
					q.append([i, a[1] + 1])
		for i in range(len(dist)):
			if dist[i] == math.inf:
				dist[i] = -1
		return dist


from queue import Queue

class Solution:

	def shortestPath(self, edges, n, m, src):
		adj = [[] for i in range(n)]
		for x in edges:
			adj[x[0]].append(x[1])
			adj[x[1]].append(x[0])
		dis = [0 for i in range(n)]
		for i in range(n):
			dis[i] = 1000000000.0
		dis[src] = 0
		q = Queue()
		q.put(src)
		while q.qsize() != 0:
			node = q.get()
			for x in adj[node]:
				if dis[node] + 1 < dis[x]:
					dis[x] = dis[node] + 1
					q.put(x)
		for i in range(n):
			if dis[i] >= 1000000000.0:
				dis[i] = -1
		return dis