Write an algorithm/code (in java or python): A cat and dog do not get along in there home. Neither should see each other before getting to their respective vertices. Given a connected, undirected graph, with nodes that represent rooms of the house and edges that represent adjacency of said rooms, find the shortest path for the cat and dog such that they are never in each others line of sight, but get to their destination vertex. Line of sight means that the dog and cat are either in adjacent rooms or in the same room. Give schedules of room locations for each of the cat and dog which together represent the shortest suitable path. The output will be two space-delineated lists of integers, separated by a line break. The first list will give the schedule for the cat, the second list will give the schedule for dog. A schedule is the sequence of vertices each must take simultaneously so that they do not occupy adjacent or the same vertices at the same time.