"""

	Нахождение кратчайшего пути (Augmented-BFS)
			
		Уникальность алгоитма BFS в том, что при добавлении пары строк он эффективно
		вычисляет расстояние кратчайшего пути.

		Задача для Единичных длин ребер (Длины ребер одинаковы и равны единице)

			Вход: неорипнтированный или орентированный граф G=(V,E) и нач. верш s->V
			Выход: dist(s,v) для каждой вершины v->V.

		ПСЕВДОКОД:

			1) Пометить s как разведанную вершину, все остальные как неразведанные
			X1) l(s):=0, l(v):=+∞ для каждой v!=s 
			2) Q:= очередь, инициализированная вершиной s
			3) While Q не является пустой do:
			3.1		Удалить вершину v из начала очереди
			3.2		for каждое ребро (v,w) в списке смежности v do
			3.2.1 		if w не разведана then
			3.2.1.1				пометить w как разведанную
			X2)						l(w):= l(v)+1
			3.2.1.2				добавить w в конец Q

			Пример:

						a			  e		
					/   \   /  
				s       c   |
					\   /   \
						b 	_		d
			
			Стартовая вершина - s.
			ПЕРВАЯ ИТЕРАЦИЯ (while): 	
				1) Извлекаем s из Q. 
				2) for проверяет ребра (s,a) и (s,b). 
				3) a и b не помечены как разведанные (if)
				4) Помечаем a и b как разведанные
				X2) l(a) = l(s)+1 --> l(a) = 0+1 -> l(a) = 1
						l(b) = l(s)+1 --> l(b) = 0+1 -> l(b) = 1
				5) Добавляем их в очередь
				Q = [a,b]; (s - вышла из очереди)
			ВТОРАЯ ИТЕРАЦИЯ (while)
				1) Извлекаем a из Q. 
				2) for проверяет ребра (s,a) и (a,c). 
				3) Пропускаем (s)-оно помечено, (c) не помечено как разведанное (if)
				4) Помечаем (c) как разведанное
				X2) l(c) = l(a)+1 --> l(c) = 1+1 -> l(c) = 2
				5) Добавляем (c) в очередь
				Q = [b,c]; (a - вышла из очереди)
			ВТОРАЯ ИТЕРАЦИЯ (while)
				Схожа со 2й, но взаиодействует с d l(d) = 2
			ЧЕТВЕРТАЯ ИТЕРАЦИЯ (while)
				Обнаруживает последнюю верину e через вершину c и устанавливает l(e)=l(c)+1 = 3

			После прохождения всех циклов для каждой вершины v l(v) = dist(s,v) = № слоя. 
"""
3b6ac0193648094d726055f47018da1927e6f94c
<mask token>

"""

	Нахождение кратчайшего пути (Augmented-BFS)
			
		Уникальность алгоитма BFS в том, что при добавлении пары строк он эффективно
		вычисляет расстояние кратчайшего пути.

		Задача для Единичных длин ребер (Длины ребер одинаковы и равны единице)

			Вход: неорипнтированный или орентированный граф G=(V,E) и нач. верш s->V
			Выход: dist(s,v) для каждой вершины v->V.

		ПСЕВДОКОД:

			1) Пометить s как разведанную вершину, все остальные как неразведанные
			X1) l(s):=0, l(v):=+∞ для каждой v!=s 
			2) Q:= очередь, инициализированная вершиной s
			3) While Q не является пустой do:
			3.1		Удалить вершину v из начала очереди
			3.2		for каждое ребро (v,w) в списке смежности v do
			3.2.1 		if w не разведана then
			3.2.1.1				пометить w как разведанную
			X2)						l(w):= l(v)+1
			3.2.1.2				добавить w в конец Q

			Пример:

						a			  e		
					/   \   /  
				s       c   |
					\   /   \
						b 	_		d
			
			Стартовая вершина - s.
			ПЕРВАЯ ИТЕРАЦИЯ (while): 	
				1) Извлекаем s из Q. 
				2) for проверяет ребра (s,a) и (s,b). 
				3) a и b не помечены как разведанные (if)
				4) Помечаем a и b как разведанные
				X2) l(a) = l(s)+1 --> l(a) = 0+1 -> l(a) = 1
						l(b) = l(s)+1 --> l(b) = 0+1 -> l(b) = 1
				5) Добавляем их в очередь
				Q = [a,b]; (s - вышла из очереди)
			ВТОРАЯ ИТЕРАЦИЯ (while)
				1) Извлекаем a из Q. 
				2) for проверяет ребра (s,a) и (a,c). 
				3) Пропускаем (s)-оно помечено, (c) не помечено как разведанное (if)
				4) Помечаем (c) как разведанное
				X2) l(c) = l(a)+1 --> l(c) = 1+1 -> l(c) = 2
				5) Добавляем (c) в очередь
				Q = [b,c]; (a - вышла из очереди)
			ВТОРАЯ ИТЕРАЦИЯ (while)
				Схожа со 2й, но взаиодействует с d l(d) = 2
			ЧЕТВЕРТАЯ ИТЕРАЦИЯ (while)
				Обнаруживает последнюю верину e через вершину c и устанавливает l(e)=l(c)+1 = 3

			После прохождения всех циклов для каждой вершины v l(v) = dist(s,v) = № слоя. 
"""