Making Pairs
By Guilherme de Lima Bernardes, UNB 
Brazil
By Guilherme de Lima Bernardes, UNB Brazil
Roberto is one of the great teachers who compose the faculty of the university of his city. Training his students for the programming marathon is one of his greatest passions even being a very difficult task. Fortunately, this semester, several students have signed up for their competitive programming discipline.
To train his students, Roberto regularly applies tests regularly, where he always divides his class into different pairs, since this year, the marathon programming teams will be formed by only two members.
Throughout the semester, analyzing the results of the evaluations and the behavior of the students in the classroom, Roberto realized that if the students chosen to form a pair have no affinity, the team performance is well inferior compared to the pair formed by students who Behavior. We can say that two students A and B have affinity if they belong to the same group of friends, that is, if they have a direct relation of friendship, or if it is possible to write a sequence of students X1, X2, X3, ..., XN, where for all i <N there is a direct relationship of friendship between students Xi and Xi + 1, with X1 = A and XN = B.
The programming marathon is approaching and Roberto has decided that he will assemble pairs composed only by students who have affinity. This way, the teams at his university will be more competitive, increasing the chances of qualifying for the next phase. As the class is crowded with students, he asked you to write a program in which given the student-friend relationships and a series of queries indicating two students, you have to determine for each query whether it is possible to assemble a pair with these two students.
The input is composed of several test cases. The first line of a test case has three integers N, M e Q (2 ≤ N ≤ 104, 0 ≤ M ≤ 105, 1 ≤ Q ≤ 103), representing, respectively, the number of students, the relations of friendship between the students and the number of inquiries. The next M lines contain two integers X and Y (1 ≤ X, Y ≤ N and X != Y) indicating that student X has a direct relationship of friendship with student Y. Then, each of the next Q lines describes a query with two integers A and B (1 ≤ A, B ≤ N and A != B), indicating the students of a possible team.
For each test case print Q lines, where the i-th line is the answer to the i-th query. If it is possible to assemble a pair with the students indicated in the query print the character 'S', otherwise print the character 'N'. Print a blank line at the end of each test case.
| Input Sample | Output Sample |
|
5 3 3 4 2 3 5 1 2 1 4 5 1 2 4 3 1 2 3 2 1 2 2 3 |
S N S N S |