You are given a non-connected graph G consisting of N nodes and M edges. A graph is said to be non-connected if it is possible to find at least one pair of nodes such that no path in the graph has those nodes as endpoints.
Your task is to answer Q queries. In each query you are given two integers a and b, and you need to compute the length (in edges) of the shortest path between nodes a and b in the complement of G. The complement of a graph G is another graph G′ that doesn't contain any of the edges present in G and contains all the edges not present in G.