In JOI Kingdom, the security of IOI Jail is strictly controlled. There are rooms in IOI Jail, numbered from
to
. There are
passages connecting rooms. The passage
(
) connects the room
and
the room
bidirectionally. It is possible to move from any room to any other room by passing through several
passages.
There are prisoners in IOI Jail. Each prisoner has an "ID number", which is an integer between
and
,
inclusive. The bedroom of the prisoner
(
) is the room
, and the workroom of the prisoner
is the
room
. A prisoner may work in the bedroom of another prisoner. However, no two prisoners share the same
bedroom, and no two prisoners share the same workroom.
One morning, the prisoners have to move from their bedrooms to their workrooms. Mr. APIO is the
director of IOI Jail. He will give the following directions to the prisoners to move.
- Direction: Choose a prisoner, and move the chosen prisoner from the current room to another room which is connected with the current room by a passage. In order to avoid communication between prisoners, it is not allowed to move the prisoner to a room where another prisoner stays.
In order to start work as early as possible, Mr. APIO wants to know whether it is possible to give directions so that every prisoner does not pass through the same room more than once (it means that every prisoner takes a shortest path).
Write a program which, given information of the rooms and the passages in IOI Jail and information on the prisoners, determines whether it is possible to move the prisoners so that every prisoner takes a shortest path.
Input Specification
A test case consists of scenarios, numbered from
to
. The following values are specified for each
scenario. For the range of these values, see Constraints.
- The number of rooms
in IOI Jail.
- Information on the passages in IOI Jail
.
- The number of prisoners
in IOI Jail.
- Information on the bedrooms and the workrooms of the prisoners
.
The format of the input data is as follows. Given values are all integers
(Input for Scenario )
(Input for Scenario )
(Input for Scenario )
The format of the input data for each scenario is as follows. See Sample Input and Output for details.
Output Specification
Write lines to the standard output. The
-th line (
) should contain the following:
Yes
if it is possible to move the prisoners for the scenario.
No
if it is not possible to move the prisoners for the scenario.
Constraints
.
.
.
.
.
.
are different from each other.
are different from each other.
.
- It is possible to move from any room to any other room by passing through several passages.
- The sum of
for the
scenarios is less than or equal to
.
Subtasks
- (5 points)
,
.
- (5 points)
,
,
.
- (16 points)
,
,
.
- (28 points)
,
,
.
- (12 points)
,
.
- (11 points) It is possible to move from any room to any other room by passing through at most
passages.
- (23 points) No additional constraints.
Sample Input 1
1
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
2
3 4
4 8
Sample Output 1
Yes
Explanation for Sample 1
For this sample input, if the director gives the following directions, it is possible to move the prisoners so that every prisoner takes a shortest path.
- Move the prisoner
from the room
to the room
.
- Move the prisoner
from the room
to the room
.
- Move the prisoner
from the room
to the room
.
- Move the prisoner
from the room
to the room
.
- Move the prisoner
from the room
to the room
.
Therefore, output Yes
. The structure of the jail for this sample input is as follows.
This sample input satisfies the constraints of all the subtasks.
Sample Input 2
2
7
1 2
2 3
3 4
4 5
3 6
6 7
2
4 1
5 7
4
1 2
1 3
1 4
3
2 3
3 4
4 2
Sample Output 2
Yes
No
Explanation for Sample 2
There are scenarios. For Scenario
, if the director gives the following directions, it is possible to move
the prisoners so that every prisoner takes a shortest path.
- Move the prisoner
from the room
to the room
.
- Move the prisoner
from the room
to the room
.
- Move the prisoner
from the room
to the room
.
- Move the prisoner
from the room
to the room
.
- Move the prisoner
from the room
to the room
.
- Move the prisoner
from the room
to the room
.
- Move the prisoner
from the room
to the room
.
However, for Scenario , it is not possible to move the prisoners so that every prisoner takes a shortest path.
Therefore, the first line of output should be Yes, and the second line of output should be
No
.
This sample input satisfies the constraints of Subtasks .
Sample Input 3
3
3
1 2
2 3
2
2 1
3 2
7
1 2
2 3
3 4
4 5
5 6
6 7
3
1 3
4 2
2 5
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4
1 5
2 6
3 7
4 8
Sample Output 3
Yes
No
Yes
Explanation for Sample 3
This sample input satisfies the constraints of Subtasks .
Comments