Hint 1:
The original graph is not bipartite.
However, you may notice that even numbers are included in one set, and odd numbers > 1 are included in another. Separately, you need to understand what to do with 1.

Hint 2:
Kuhn's Algorithm for Maximum Bipartite Matching for bipartite graph (even numbers, odd numbers > 1 and ones)

Some tests:

10
2 4 6 8 5 7 1 1 9 2
->
YES
2 5
4 7
8 9
6 1
2 1

6
2 4 6 8 1 5
->
NO

12
1 1 1 1 1 2 3 4 5 6 7 8
->
YES
8 3
2 5
6 7
4 1
1 1
1 1

Edited by author 29.07.2025 22:35