## Art Academy III: Sabotage

View as PDF

Points: 20 (partial)
Time limit: 0.6s
Java 8 1.0s
PyPy 2 3.0s
PyPy 3 3.0s
Memory limit: 768M

Author:
Problem types

After hewmatt10's one and only friend, astrocat879, left his Art Academy, hewmatt10 had been running all across the city in hopes of finding someone that he can replace. Searching far and wide, he eventually stumbles upon the love of his life: [REDACTED]. Wanting to see whether or not hewmatt10 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.

hewmatt10, not wanting to risk his only chance, is relying on YOU to help him. However, because you do NOT want to help him, you have decided to do the EXACT OPPOSITE of what he asks - perform operations such that the absolute difference is EQUAL to .

#### 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.

#### Constraints

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.

#### 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 between groups and is equal to .