How to Survive while Visiting a Graph