After kidnap love. Searching far and wide, he eventually stumbles upon the love of his life: [REDACTED] . Wanting to see whether or not is worthy, [REDACTED] gives him a seemingly impossible task, defined as such:
You are given an undirected, acyclic graph with
nodes and
edges, such that
. In other words, you are given a forest of trees. You are also given a special value, called
. Each node will be associated with a group
, where
.
For each connected component, you may choose to do ONE of the following operations:
Operation Description 0 Do nothing with this component. 1 Increase every node's group by 1. 2 Multiply every node's group by 2. 3 Take the bitwise XOR of every node's group by 15. You must perform operations such that the absolute difference between the number of nodes between two groups
and
is as FAR AWAY as
as possible. You will be asked to do this
times.
.
Input Specification
The first line will contain the integers ,
,
, and
.
,
,
,
.
The next line will contain spaced integers
,
, representing the group of node
.
The next lines will contain two spaced integers
and
, indicating that nodes
and
are connected
.
The next lines will contain three spaced integers
,
and
,
.
Output Specification
For each of the questions, output a
YES
if it is possible to get groups and
to have an absolute difference of
, and a
NO
otherwise, followed by a newline.
If the answer is YES
, this will then be followed by spaced integers
, followed by a newline, where
corresponds to the type of operation performed on node
's connected component to reach
. If there are multiple such ways to perform operations, print the arrangement that is lexicographically least.
Clarification: Arrangement refers to the spaced integers on the second line.
Subtasks
For this problem, you will NOT be required to pass the sample to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.
Subtask | Description | Points |
---|---|---|
1 | 10 | |
2 | 10 | |
3 | No further constraints. | 80 |
Sample Input
10 7 4 1
1 2 3 3 4 2 3 3 3 2
1 2
1 3
2 4
3 7
5 8
5 9
6 10
1 3 6
Sample Output
YES
0 0 0 0 0 1 0 0 0 1
Explanation
Operation can be performed on the connected component containing nodes
and
. After performing this operation, there will be
nodes with group
, and
node with group
. This is the lexicographically least way to perform operations such that the absolute difference bewteen groups
and
is equal to
.
Comments