big-p-and-party-1

Big P has recently become very famous among girls .

Big P goes to a party and every girl present there wants to dance with him. However, Big P cannot dance with all of them, because there are many of them.

Now if a girl gets to dance with Big P, she considers herself to be  " 1-Lucky ". A person that dances with someone who has danced with a person who has danced with Big P considers themselves  " 2-Lucky ", and so on.

The Luckiness is defined on the basis of above mentioned rule. ( 1-Lucky -> Luckiness = 1).

Note1: Luckiness of Big P is 0 .

Note2: No one has negative luckiness.

Note3: If a person's luckiness cannot be determined from the above rules (he/she has not danced with anyone with finite luckiness), his/her luckiness is INF (infinity).

Note4: If a person A is not Big P himself, and has danced with someone with luckiness X, and has not danced with anyone with Luckiness smaller than X, then A has luckiness X+1 .

Input Format:

The first line has two numbers A,number of persons in the party and B, number of dancing couples Then B lines follow, each containing two distinct persons, denoting that the two persons have danced. Persons are represented by numbers between 0 and A-1. 

Big P is represented by 0.

Output Format:

Output A-1 lines , ith line containing the luckiness of ith person. (1 ≤ i ≤ A-1)

If luckiness cannot be calculated for a person - print "-1"(without the quotes).

[A ≤ 1000 , B ≤(A*(A-1))/2 ]

SAMPLE INPUT
5 6
0 1
0 2
3 2
2 4
4 3
1 2

SAMPLE OUTPUT
1
1
2
2

Difficulty: MEDIUM
Tags: Graph algorithms

Graph traversal

Starter code:

Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import sys
vals = input().split(" ")
A, B = [int(x) for x in vals]
graph, distTo, marked =[],[],[]
for i in range(A):
	graph.append([])
	marked.append(False)
	distTo.append(-1)
	
distTo[0] = 0

while B > 0:
	x, y = [int(x) for x in input().split(" ")]
	graph[x].append(y)
	graph[y].append(x)
	B -=1
 
 
#BFS
from collections import deque

queue = deque([])
queue.append(0)
while queue:
	s = queue.popleft();
	marked[s]= True
	for w in graph[s]:
		if marked[w]: continue
		queue.append(w)
		marked[w] = True
		distTo[w] = distTo[s]+1

for i in range(1,len(distTo)):
	print(distTo[i])


# Big P and Party
# BFS
def give_ranks(DANCES,RANK,n):
	visited, queue = set(), [n]
	while queue:
		vertex = queue.pop(0)
		r=RANK[vertex]+1
		for d in DANCES[vertex]:
			if RANK[d]==-1:
				RANK[d]=r
			elif RANK[d]>r:
				RANK[d]=r
		if vertex not in visited:
			visited.add(vertex)
			queue.extend(DANCES[vertex] - visited)
			r+=1

DANCES={}
a,b=list(map(int,input().split(" ")))
for i in range(0,a):
	DANCES[i]=set([])
for i in range(0,b):
	x,y=list(map(int, input().split(" ")))
	l=list(DANCES[x])
	l.append(y)
	DANCES[x]=set(l)
	l=list(DANCES[y])
	l.append(x)
	DANCES[y]=set(l)
RANK=[]
for i in range(0,a):
	RANK.append(-1)
n=0
RANK[n]=0
give_ranks(DANCES,RANK,n)
for r in RANK[1:]:
	print(r)


def big_p():
	a,b = list(map(int,input().split()))
	luck =[a]*a; luck[0]=0
	link=[]
	for each in range(a):
		link.append([])
	for each in range(b):
		p1,p2 = list(map(int,input().split()))
		link[p1].append(p2)
		link[p2].append(p1)

	level = 1
	queue = [link[0]]
	while queue:
		net = []
		element = queue.pop(0)
		for i in element:
			if level<luck[i]:
				luck[i] = level
				net +=link[i]
		if net:
			queue.append(net)

		level+=1
	for i in luck[1:]:
		if i==a:
			print('-1')
		else:
			print(i)
		
	

big_p()


import queue
A, B = [int(val) for val in (input().split(" "))]
edges = [[-1 for i in range(A)]for j in range(A) ]
lucks = [-1 for i in range(A)]
lucks[0] = 0
for k in range(B):
	x, y = [int(val) for val in (input().split(" "))]
	edges[x][y] = 1
	edges[y][x] = 1
q = queue.Queue(A)
q.put(0)
while(not q.empty()):
	cur = q.get()
	cur_luck = lucks[cur] + 1
	for i in range(1,A):
		if( edges[cur][i] == 1 and (lucks[i]>cur_luck or lucks[i]==-1 ) ):
			lucks[i] = cur_luck
			q.put(i)   
for i in range(1,A):
	print(lucks[i])


def big_p():
	a,b = list(map(int,input().split()))
	luck =[a]*a
	luck[0]=0
	link=[]
	for each in range(a):
		link.append([])
	for each in range(b):
		p1,p2 = list(map(int,input().split()))
		link[p1].append(p2)
		link[p2].append(p1)
 
	level = 1
	queue = [link[0]]
	#print(queue)
	while queue:
		net = []
		element = queue.pop(0)
		#print("ele",element)
		for i in element:
			if level<luck[i]:
				luck[i] = level
				net +=link[i]
		if net:
			queue.append(net)
 
		level+=1
	for i in luck[1:]:
		if i==a:
			print('-1')
		else:
			print (i)
		
	
 
big_p()

		


def bfs(x):
	b=[False]*(n+1)# an array of false flags to keep track of vertices visited
	#memo=[-1]*(n+1)
	global memo
	
	q=[]
	q.append(x)
	memo[x]=0
	while len(q)!=0:
		#t=s[-1]
		top=q.pop(0)
		#print "top",top
		#l=t
		b[top]=True
		#q.pop(0)
		for j in G[top]:
			#print "j",j
			if b[j]==False:
			   
			
				q.append(j)
				memo[j]=1+memo[top]
				b[j]=True

n,m=list(map(int,input().split()))
G={i:[] for i in range(n)}
memo=[-1]*(n)
memo[0]=0
p=m
while p!=0:
	x,y=list(map(int,input().split()))
	G[x].append(y)
	G[y].append(x)
	p-=1
bfs(0)   
for i in range(1,n):
	print(memo[i])    


def main():
	[N,t] = [int(each) for each in input().split()]
	luck = [N] * N; luck[0] = 0
	link = []
	for each in range(N):
		link.append([])

	for each in range(t):
		[p1,p2] = [int(each) for each in input().split()]
		link[p1].append(p2)
		link[p2].append(p1)
	#print "luck ", luck
	#print "link ", link

	level = 1
	queue = [link[0]]
	while queue:
		next_element = []
		element = queue.pop(0)
		#print "element", element
		for i in element:
			if level < luck[i]:
				luck[i] = level
				next_element += link[i]
		if next_element:
			queue.append(next_element)
		level += 1

	for each in luck[1:]:
		if each == N:
			print('-1')
		else:
			print(each)
main()