QN02 - Seating Arrangement

Problem Statement

In DA-IICT, 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.



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.

: All student IDs are unique, and range from 0 to n-1.



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 case-sensitive.




7 4
1 2
2 3
1 3
4 5
1 3
4 6
5 1
5 4



hide comments
geeta: 2017-04-15 09:10:24

compiling with c++(gcc 6.3) gives compilation error -_-

aeon: 2017-01-07 17:22:04

easy DSU, use path compression technique

SUBHAM SANGHAI: 2016-05-31 21:15:02

Why is the tag bitmask? Can be easily solved using DSU

Atul Kashyap: 2012-12-28 04:46:17

applying bfs gives tle....any other hint....

(Tjandra Satria Gunawan)(曾毅昆): 2012-12-23 18:34:29

@Paul Draper: Yes, I see ;-)

Paul Draper: 2012-12-23 02:08:27

IMPORTANT: Friendship is also reflexive. A person is always friends with himself.
For example,
1 0
0 0

(Many WA before I figured this out.)

And @Tjandra, it's been solved in Java.

Paul Draper: 2012-12-22 23:34:49

@Tjandra, there are more languages than C in the world.

(Tjandra Satria Gunawan)(曾毅昆): 2012-12-22 22:35:27

Need some 'NZEC experiment' to find out tricky test case, finally AC ;-) Nice problem...

Last edit: 2012-12-23 01:48:25

Added by:Gowri Sundaram
Time limit:1s-1.655s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64