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 in spite 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 at least 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 n-1.

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

 

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

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

hide comments
2017-01-07 17:22:04 aeon
easy DSU, use path compression technique
2016-05-31 21:15:02 SUBHAM SANGHAI
Why is the tag bitmask? Can be easily solved using DSU
2012-12-28 04:46:17 Atul Kashyap
applying bfs gives tle....any other hint....
2012-12-23 18:34:29 (Tjandra Satria Gunawan)(曾毅昆)
@Paul Draper: Yes, I see ;-)
2012-12-23 02:08:27 Paul Draper
IMPORTANT: Friendship is also reflexive. A person is always friends with himself.
For example,
1 0
1
0 0
yields
YES

(Many WA before I figured this out.)

And @Tjandra, it's been solved in Java.
2012-12-22 23:34:49 Paul Draper
@Tjandra, there are more languages than C in the world.
2012-12-22 22:35:27 (Tjandra Satria Gunawan)(曾毅昆)
Need some 'NZEC experiment' to find out tricky test case, finally AC ;-) Nice problem...

Last edit: 2012-12-23 01:48:25
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.