The Clash-Free Partition

You have N items (N is even), each with a weight. You must divide them into exactly two groups of size N/2 such that the total weight of both groups is equal. However, some items 'clash' and cannot be placed in the same group. Determine if such a partition is possible. Input: First line N and M (number of clash pairs). Second line N integers (weights). Next M lines contain clash pairs (indices 0 to N-1). Example: Input: 4 1 10 10 10 10 0 1 Output: YES (Explanation: Group A: {0, 2}, Group B: {1, 3}. Weights are 20 vs 20. 0 and 1 are in different groups, satisfying the clash.)