Вам задан неориентированный граф без петель и кратных ребер, состоящий из \(n\) вершин и \(m\) ребер. Также вам задано три числа \(n_1\), \(n_2\) и \(n_3\).
Определите, можно ли расставить в вершины графа цифры 1, 2 и 3 так, чтобы выполнялись следующие условия:
- В каждой вершине должно стоять ровно одно из чисел 1, 2, 3;
- Суммарно количество чисел 1 во всех вершинах должно равняться \(n_1\);
- Суммарно количество чисел 2 во всех вершинах должно равняться \(n_2\);
- Суммарно количество чисел 3 во всех вершинах должно равняться \(n_3\);
- Для каждого ребра \((u, v)\) должно быть верно \(|col_u - col_v| = 1\), где \(col_x\) — цвет вершины с индексом \(x\).
Если существует несколько раскрасок, удовлетворяющим все описанным выше условиям, разрешено найти любую из них.
Выходные данные
Если существует раскраска, удовлетворяющая всем описанным условиям, выведите в первую строку «YES» (без кавычек). Во вторую строку выведите строку длины \(n\), состоящую только из цифр 1, 2 и 3, причем \(i\)-й символ этой строки должен быть равен цифре, которую нужно поставить в \(i\)-ю вершину.
Если подходящей раскраски не существует, выведите «NO» (без кавычек).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
2 2 2
3 1
5 4
2 5
|
YES
112323
|
|
2
|
5 9
0 2 3
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
|
NO
|