PROGRAMMING:Criminal gang
Tabu's police department decided to end the chaos, so it had to take action to eradicate several of the city's major gangs. The question now is, given two criminals, do they belong to the same gang? How many gangs are there in the city? Suppose that there are n criminals in tabu City, whose numbers are 1 to N, and M messages are given to indicate the numbers of two criminals belonging to the same gang. Please help the police calculate the information they want based on the incomplete information.
###Input format:
Enter the first line of three positive integers, N, m and Q. N is the number of criminals; M is the number of known information given; Q is the number of queries. Next, there are two positive integers a and B in each line, indicating that criminal a and criminal B belong to the same gang. Next, line Q contains two positive integers C and D in each line. That is to query whether criminals C and D belong to the same gang. The integers in each line are separated by spaces, and N, m and Q are not more than 1000.
###Output format:
The output is Q + 1 line. The first Q line corresponds to the results of Q queries. If it belongs to the same gang, it outputs "in the same gang." otherwise, it outputs "in different gangs.". The last line is an integer indicating the number of gangs.
###Input example:
```in
3 2 1
1 2
2 3
1 3
```
###Output example:
```out
In the same gang.
one
```
answer：If there is no answer, please comment
###Input format:
Enter the first line of three positive integers, N, m and Q. N is the number of criminals; M is the number of known information given; Q is the number of queries. Next, there are two positive integers a and B in each line, indicating that criminal a and criminal B belong to the same gang. Next, line Q contains two positive integers C and D in each line. That is to query whether criminals C and D belong to the same gang. The integers in each line are separated by spaces, and N, m and Q are not more than 1000.
###Output format:
The output is Q + 1 line. The first Q line corresponds to the results of Q queries. If it belongs to the same gang, it outputs "in the same gang." otherwise, it outputs "in different gangs.". The last line is an integer indicating the number of gangs.
###Input example:
```in
3 2 1
1 2
2 3
1 3
```
###Output example:
```out
In the same gang.
one
```
answer：If there is no answer, please comment