Description

     After the "common longest substring" problem, it occurred to professor HT Chen that he forgot to set the third problem. It's difficult for HT to give a proper problem at this midterm. Suddenly, he sees a map on the table, and a idea appear in his mind.

     There are some cities on the map,  some roads connecting some of them. And, there are only one road between two connected cities, of course, all of the roads are undirected. The figure below is an example of the problem instance. City 1, 6, 2 are connected, and 4, 5 are also connected by the other route. City 3 isn't connected with any other city. Now, HT hopes you guys to find that if there is a route from one city to another one.

Hint. You can use 2-D array to record the road between the city, and use some characters to indicate where  the road is. For example, you can use array to store the data, and just modify the data in array then you can get the answer.

 

 

Hint. You can judge that two cities is connected to the same city or not. If so, these three cities may connected together.

Hint. Mutiple for loop might be used in this problem.

 

You can see the sample code for all the hint. 

#include <stdio.h> #include <stdlib.h> int main() { int i, j, k; int city, con; int a, b; int Map[?][?]; /* You must initialize something here! */ scanf("%d%d", &city, &con); for(i=1; i<=con; i++){ scanf("%d %d", &a, &b); // Store the data here! } // Remember to modify the ??? in the for loop! for(k=1; k<= ??? ; k++){ for(i=1; i<= ??? ; i++){ // Somrthing might be writed here or not! for(j=1; j<= ??? ; j++){ // The most important judge might be writed here! } } } int test; scanf("%d", &test); for(i=0; i<test; i++){ scanf("%d %d", &a, &b); // Write your output type here! } return 0; }

Input

The first element (called C) of first line  is the how many cities on the map. The second element  (called N) of first line is the number of road on the map. Each of the next N lines contains two numbers A and B. That means the city A and the city B are connected by one road. And after the first line and N lines, it will be one line that only contains one number T. T is the number of the problem that Jason want to know. So, after T, the next T lines represents the problem. Each of T lines include two numbers X and Y, and you need to print the connection is between  city X and city Y or not.

In the end, It is guaranteed that :

•  0 <=  C  <=  1000
•  0 <=  N  <=  C²
•  0 <=  T  <=  C²

 

Output

You need to print the connection is between  city X and city Y or not. And you need to print '\n' after each answer.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss