시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

N (1 <= N <= 1000) cows, conveniently numbered 1..N all attend a tea time every day. M (1 <= M <= 2,000) unique pairs of those cows have already met before the first tea time. Pair i of these cows who have met is specified by two differing integers A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N). The input never indicates that cows have met each other more than once.

At tea time, any cow i and cow j who have met a mutual friend cow k will meet sometime during that tea time and thus expand their circle of known cows.

Determine whether Q (1 <= Q <= 100) pairs of cows have met after tea times are held for long enough that no new cow meetings are occurring. Query j consists of a pair of different cows X_j and Y_j (1 <= X_j <= N; 1 <= Y_j <= N).

For example, suppose that out of cows 1 through 5, we know that 2 has met 5, 2 has met 3, and 4 has met 5; see (a) below.

   2---3           2---3            2---3
    \              |\  |            |\ /|
1    \     -->  1  | \ |    -->  1  | X |
      \            |  \|            |/ \|
   4---5           4---5            4---5
    (a)             (b)              (c)

In the first tea time, cow 2 meets cow 4, and cow 3 meets cow 5; see (b) above. In the second tea time, cow 3 meets cow 4; see (c) above.

입력

  • Line 1: Three space-separated integers: N, M, and Q
  • Lines 2..M+1: Line i+1 contains two space-separated integers: A_i and B_i
  • Lines M+2..M+Q+1: Line j+M+1 contains query j as two space-separated integers: X_j and Y_j

 

출력

  • Lines 1..Q: Line j should be "Y" if the cows in the jth query have met and "N" if they have not met.

 

예제 입력

5 3 3
2 5
2 3
4 5
2 3
3 5
1 5

예제 출력

Y
Y
N

힌트