## Task Description

You are going to write a program to check whether two cities are connected by a path. There are unknown number of cities and $M$ roads. Every road connects two cities. Two cities $a$ and $b$ are connected by a path, i.e., a sequence of cities, where the first city in the path is $a$, the last city is $b$, and every two adjacent cities in the sequence are connected by a road.

Please refer to the following figure.
Each road is represented by a pair of city indices.
You need to build an object to store these roads.
Note that the indices of cities is from $0$ to a very large $N$, therefore you *cannot* use two dimensional array to store the roads as before, or your program will get a **RE** or an **MLE**.
Then, you will be given a sequence of pairs of city indices, and determine if the two cities are connected by a path or not.

We suggest the following approach to solve this problem.
First, design a structure *Graph*, and put all roads into *Graph*.
Then, sort these roads by their starting city indices.
As a result, all roads from the same city will be placed together for easy access.
You need to use *qsort* to quickly sort these roads.
Using a *bubble sort* will cause **TLE**.
Please refer to Figure 1.

Then, build a mapping array from the city index to the first road leaving this city.
That is, when given a city index, we can easily find the destination of all roads leaving the city from *Graph*.
One easily build this mapping in which the indices in the mapping are sorted from the sorted edge sets.
Please refer to Figure 2.

Finally, you need to determine if a given pair of city indices, $a$ and $b$, are connected by a path or not.
For this we suggest the following approach.
First we use a *binary search* to search the map for $a$, and get the pointer into *Graph* for all cities that $a$ can reach.
For example, city $3$ can reach cities 2, 10, and 50.
Then we recursively go from these cities and see if we reach $b$.
Note that you need to remember the set of cities you have already visited so you do not visit the same city twice.

We suggest the following structure and functions.

`#include <stdbool.h>`

`typedef`

`struct`

`_graph {`

` `

`// design your object here`

`} Graph;`

`typedef`

`struct`

`_map{`

` `

`// design your object here`

`} Map`

`void`

`init(Graph *graph, `

`int`

`M); `

`// initialize graph`

`void`

`addRoad(Graph *graph, `

`int`

`city1, `

`int`

`city2); `

`// add roads into graph`

`void`

`normalized(Graph *graph, Map *map) `

`// sort the roads by indices and build the map. `

`bool`

`hasPath(Graph *graph, Map *map, `

`int`

`city1, `

`int`

`city2);`

`// check if two cities are connected`

## Input Format

The first line contains one integer $M$, the number of roads in the graph. Each of the following $M$ lines contains two city indices of a road. The next line contains one integer $Q$, the number of queries. Each of the following $Q$ lines contains two city indices to check if there is a path between them.

- $M \leq 10000$
- $Q \leq 200$

## Output Format

For each query, print “There is a path.” when there is a path between the given two cities, otherwise print “There is no path.”.

## Sample input 1

`6`

`100 2`

`3 50`

`50 2`

`3 10`

`20 200`

`3 2`

`8`

`200 20`

`20 200`

`100 10`

`50 100`

`100 200`

`30 2`

`3 40`

`30 40`

## Sample output 1

`There is a path.`

`There is a path.`

`There is a path.`

`There is a path.`

`There is no path.`

`There is no path.`

`There is no path.`

`There is no path.`