**PROBLEM LINK:** [Contest][1]

**DIFFICULTY:** Medium

**PREREQUISITES:** Graphs

**PROBLEM:**

The aim is to find the number of cities from source to destination.

If the source and destination are different a BFS traversal with each layer adding city to path, will be counted.

If source and destination are same, still a BFS has to be applied to find a cycle path.

Also, there is a possibility that the path does not exists.

**SETTER’S SOLUTION:** [Solution Link][2]

**APPROACH:**

We need an array **dist** to store the distances from S to E.

For BFS, we need **queue q** to store traversal nodes (cities), global array **visited** to store which nodes (cities) have been visited already.

A simple BFS from node (city) S has to be run. Complexity of this solution is O(N+M).

From S we add each layer by layer increment each child node’s distance from S to be its distance from parent node+1. Here each node specifies each city and after traversal, we can check the visited array has city E i.e. index E visited or not. If it is visited, we print **dist[E]** along with **YES** else we print **NO.**

[1]: Contest Page | CodeChef

[2]: IO6t9o - Online C++0x Compiler & Debugging Tool - Ideone.com