QN02  Seating Arrangement
Problem Statement
In DAIICT, the end sems are just around the corner and it seems like all the students are working very hard. But it's not just students, the professors are hard at work too. In particular, the Dean (Students) is very busy working out the exam seating arrangements for all the students.
Now normally, as we all know, the benches in each of the exam halls can seat exactly 2 students. Also, it is ensured that every bench contains exactly 2 students from different batches (so that there is no copying). But inspite of this, the Dean has noticed that even if the 2 students are from totally different batches, if they are friends, then they tend to help each other (or atleast try to, depending on how much they both know). The Dean wants to prevent this, so the seating arrangement is such that no two friends sit side by side during any exam, so that the students prepare well for the exams. But he is falling short of ideas to work this out.
Please help him out. You are given a list of pairs of IDs ( A, B ), such that the student with ID A is friends with the student with ID B. For every query ( C, D ) please print out whether or not these 2 students are friends ( meaning they cannot be seated with each other ).
Note: In this case, please assume friendship to be both symmetric and transitive. That is, if A is friends with B, B is also friends with A. Moreover, if A and B are friends and B and C are friends, this implies that A and C are also friends.
Input
The input comprises of several lines. The first line contains 2 integers  n and m, where n is the number of students who will be writing the exam ( 2 <= n <= 100000 ) and m is the number of pairs of student IDs in the input. ( 0 <= m <= 100000. Also m <= n*( n+1 ) / 2 ).
This is followed by m lines of the form : A B
This indicates that the student with ID A is friends with the student with ID B. ( 0 <= A,B < n ).
This is followed by a line containing a single integer q ( 1 <= q <= 100000 ) indicating the number of queries you have to answer. q lines of queries follow. Each query consists of a single line containing 2 space separated integers C and D. ( 0 <= C,D < n ). These are the 2 student IDs for which you have to state whether or not they are friends.
Note : All student IDs are unique, and range from 0 to n1.
Output
For each query, output a single line with "YES" if the 2 students are friends, and "NO" otherwise. Please note that the quotes are just for clarity, and that the output is casesensitive.
Example
Input:
7 4
1 2
2 3
1 3
4 5
4
1 3
4 6
5 1
5 4
Output:
YES
NO
NO
YES
hide comments
geeta:
20170415 09:10:24
compiling with c++(gcc 6.3) gives compilation error _ 

aeon:
20170107 17:22:04
easy DSU, use path compression technique 

SUBHAM SANGHAI:
20160531 21:15:02
Why is the tag bitmask? Can be easily solved using DSU 

Atul Kashyap:
20121228 04:46:17
applying bfs gives tle....any other hint.... 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121223 18:34:29
@Paul Draper: Yes, I see ;) 

Paul Draper:
20121223 02:08:27
IMPORTANT: Friendship is also reflexive. A person is always friends with himself.


Paul Draper:
20121222 23:34:49
@Tjandra, there are more languages than C in the world. 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121222 22:35:27
Need some 'NZEC experiment' to find out tricky test case, finally AC ;) Nice problem... Last edit: 20121223 01:48:25 
Added by:  Gowri Sundaram 
Date:  20121112 
Time limit:  1s1.655s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 