Three-Day Tourist Partition

Fatima plans to visit all the attractions in Baku over three days. There are (n) attractions (numbered from (0) to (n-1)) and (m) bidirectional roads connecting them. The entire network is connected so that there is a route between any two attractions. Fatima has decided that on day 1 she will visit (a) attractions, on day 2 (b) attractions, and on day 3 (c) attractions (thus (a+b+c=n)). She wants to partition the attractions into three sets (A), (B) and (C) with sizes (a), (b) and (c) respectively, such that at least two of these sets induce a connected subgraph. Here, a set (S) is defined as connected if for every two attractions in (S) there exists a path using only the roads connecting vertices in (S).

Your task is to find any legal partition of attractions into (A), (B) and (C) (represented by labels 1, 2, 3 respectively) that meets the above condition, or determine that no legal partition exists.

Function Specification

Implement the following function:

[ int[] find_split(int n, int a, int b, int c, int[] p, int[] q) ]

where:

• n is the number of attractions.
• a, b, and c are the required sizes of sets \(A\), \(B\), and \(C\) respectively.
• p and q are arrays of length \(m\) representing the endpoints of each road. For each \(i\) (\(0 \le i \le m-1\)), there is a road between attractions \(p[i]\) and \(q[i]\).

The function should return an array of length (n) where the (i^{th}) element is either 1, 2, or 3 indicating to which set attraction (i) is assigned. If no legal partition exists, return an array of (n) zeros.

Note: A legal partition is one in which at least two of the three sets form connected induced subgraphs (i.e. the attractions in that set are connected by roads without leaving the set).

inputFormat

The first line contains five integers: (n), (a), (b), (c) and (m). Each of the following (m) lines contains two integers, representing a road between two attractions (0-indexed).

outputFormat

Output (n) integers separated by spaces. The (i^{th}) integer should be 1, 2, or 3 indicating the assignment of attraction (i) to set (A), (B), or (C) respectively, or all zeros if no legal partition exists.

sample

6 2 2 2 5
0 1
1 2
2 3
3 4
4 5

1 1 2 2 3 3