title: Breadth First Search in O(log n)
body: <p>Is it possible to find the destination from a source in O(log n) time using BFS (using min vertices traversed) in an undirected graph with loop and negative edges?</p>
  
  <p>For ex:
  You are given a simple connected graph G with N vertices and N edges (a simple graph is an un-directed graph that has no loops and no more than one edge between any two different vertices).
  It is obvious that the graph G contains exactly one cycle and you can assume that the length of this cycle is odd (there are odd number of vertices in this cycle).
  The vertices are numbered from 1 to N. Each edge is assigned a corresponding integer weight.
  Your mission is to stimulate two types of queries :
  Update query represented by f u v: change the sign of all the weights of the edges on the shortest path (you can see the definition of shortest path in this problem later on) from vertex u to vertex v.
  Find query represented by ? u v: On the shortest path from vertex u to vertex v, find the (possibly empty) set of consecutive edges such that the sum of the weights is maximal. In other words, let's define the shortest path from u to v as a_1, a_2, ..., a_k (where a_1 = u and a_k = v). You have to find a_i and a_j such that i &lt;= j and the sum of the weights of the edges of the path a_i, a_(i + 1), ..., a_j is as large as possible. You just have to find that sum.
  The shortest path between two vertices u and v is the path connecting them with the minimal number of vertices. In this problem, it is obvious that there is only one shortest path between any pair of vertices of G.</p>