Məsələlər
Hedge Mazes
Hedge Mazes
The Queen of Nlogonia is a fan of mazes, and therefore the queendom's architects built several mazes around the Queen's palace. Every maze built for the Queen is made of rooms connected by corridors. Each corridor connects a di erent pair of distinct rooms and can be transversed in both directions.
The Queen loves to stroll through a maze's rooms and corridors in the late afternoon. Her servants choose a di erent challenge for every day, that consists of nding a simple path from a start room to an end room in a maze. A simple path is a sequence of \textit{distinct} rooms such that each pair of consecutive rooms in the sequence is connected by a corridor. In this case the first room of the sequence must be the start room, and the last room of the sequence must be the end room. The Queen thinks that a challenge is good when, among the routes from the start room to the end room, \textit{exactly} one of them is a simple path. Can you help the Queen's servants to choose a challenge that pleases the Queen?
For doing so, write a program that given the description of a maze and a list of queries de ning the start and end rooms, determines for each query whether that choice of rooms is a good challenge or not.
\InputFile
Each test case is described using several lines. The first line contains three integers \textbf{R}, \textbf{C} and \textbf{Q} representing respectively the number of rooms in a maze (\textbf{2} ≤ \textbf{R} ≤ \textbf{10^4}), the number of corridors (\textbf{1} ≤ \textbf{C} ≤ \textbf{10^5}), and the number of queries (\textbf{1} ≤ \textbf{Q} ≤ \textbf{1000}). Rooms are identi ed by di erent integers from \textbf{1} to \textbf{R}. Each of the next \textbf{C} lines describes a corridor using two distinct integers \textbf{A} and \textbf{B}, indicating that there is a corridor connecting rooms \textbf{A} and \textbf{B} (\textbf{1} ≤ \textbf{A} < \textbf{B} ≤ \textbf{R}). After that, each of the next \textbf{Q} lines describes a query using two distinct integers \textbf{S} and \textbf{T} indicating respectively the start and end rooms of a challenge (\textbf{1} ≤ \textbf{S} < \textbf{T} ≤ \textbf{R}). You may assume that within each test case there is at most one corridor connecting each pair of rooms, and no two queries are the same.
The last test case is followed by a line containing three zeros.
\OutputFile
For each test case output \textbf{Q+1} lines. In the \textbf{i}-th line write the answer to the \textbf{i}-th query. If the rooms make a good challenge, then write the character '\textbf{Y}' (uppercase). Otherwise write the character '\textbf{N}' (uppercase). Print a line containing a single character '\textbf{-}' (hyphen) after each test case.
Giriş verilənləri #1
��6 5 3 1 2 2 3 2 4 2 5 4 5 1 3 1 5 2 6 4 2 3 1 2 2 3 1 4 1 3 1 2 0 0 0
Çıxış verilənləri #1
��Y N N - N Y Y -