Minimizing Voting Conflict in Kindergarten

There are \(n\) kindergarten children who are about to decide by voting whether to take a nap. Each child has an initial vote preference: 1 means nap and 0 means no nap. However, since the nap decision is not very important for them, they choose to demonstrate courtesy by sometimes voting contrary to their own preference in order to accommodate their good friends.

The conflict score of a vote configuration is defined as the sum of the following two parts:

• The number of pairs of good friends who end up voting differently.
• The number of children whose actual vote is different from their initial preference.

Your task is to determine for each child whether they should vote 0 or 1 so that the overall conflict score is minimized. In case of multiple optimal solutions, output any one of them.

Note: Good friendships are given as pairs, and each pair contributes a cost of 1 if the two children vote differently, counted only once per pair.

Mathematically, if we denote the vote of child \(i\) by \(v_i\) (either 0 or 1) and its intended vote by \(p_i\), and if \(E\) is the set of friendship pairs, the conflict score is:

\[ \text{Conflict} = \sum_{(i,j)\in E} \mathbf{1}_{\{v_i\neq v_j\}} + \sum_{i=1}^{n} \mathbf{1}_{\{v_i\neq p_i\}}. \]

inputFormat

The first line contains two integers \(n\) and \(m\), where \(n\) is the number of children and \(m\) is the number of pairs of good friends.

The second line contains \(n\) integers \(p_1, p_2, \ldots, p_n\), each being either 0 or 1, representing the initial vote preferences of the children.

The following \(m\) lines each contain two integers \(u\) and \(v\) (1-indexed), indicating that child \(u\) and child \(v\) are good friends.

outputFormat

Output a single line containing \(n\) space-separated integers. The \(i\)-th integer is the vote (either 0 or 1) that child \(i\) should cast in order to minimize the total conflict score.

sample

3 2
1 0 1
1 2
2 3

1 1 1

</p>