10959 - The Party, Part I

Difficulty : medium

Solution Description :

Graph (BFS) Problem

For Input:
5 5
0 1
1 2
2 3
3 4
0 4

0 step: you got person 0 (Giovanni)
1 step: you got persons 1 and 4. because 1 and 4 are dancing partner of 0 step person 0.
2 step: you got persons 2 and 3. because 2 is dancing partner of 1 (1 step) and 3 is dancing partner of 4.
Now you got all person
so ans is:
person - step
   1      -   1
   2      -   2
   3      -   2
   4      -   1

This is a simple BFS problem
Run BFS from person 0 with step 0.
Find adjacency of 0 and push to queue with step of person 0 + 1
continue the process until the queue is not empty.
Now print the step number where you got this person.