• You are given the problem of finding whether 6-degrees of separation holds between a particular 2 people in the world. E.g. checking if you and your favorite celebrity are connected in at most 6 friendship edges (e.g. you-f1-f2-f3-f4-f5-celebrity).
• A solution is not just a Yes/No answer, but also the path and the ideal solution is one that indicates the shortest connection length.
• Let`s assume you have the list of all friends for all people in the world and that everyone has exactly b=100 friends and that there are 6 billionpeople in the world.

Now consider the bi-directional search approach for this problem. What is the best basic algorithm (BFS or DFS) to use in the two directions of the bi-directional search? What is the corresponding properties (complete? optimal? worst case time and space complexity?