E. Раскраска графа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан неориентированный граф без петель и кратных ребер, состоящий из $$$n$$$ вершин и $$$m$$$ ребер. Также вам задано три числа $$$n_1$$$, $$$n_2$$$ и $$$n_3$$$.

Определите, можно ли расставить в вершины графа цифры 1, 2 и 3 так, чтобы выполнялись следующие условия:

  1. В каждой вершине должно стоять ровно одно из чисел 1, 2, 3;
  2. Суммарно количество чисел 1 во всех вершинах должно равняться $$$n_1$$$;
  3. Суммарно количество чисел 2 во всех вершинах должно равняться $$$n_2$$$;
  4. Суммарно количество чисел 3 во всех вершинах должно равняться $$$n_3$$$;
  5. Для каждого ребра $$$(u, v)$$$ должно быть верно $$$|col_u - col_v| = 1$$$, где $$$col_x$$$ — цвет вершины с индексом $$$x$$$.

Если существует несколько раскрасок, удовлетворяющим все описанным выше условиям, разрешено найти любую из них.

Входные данные

В первой строке следуют два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 5000$$$; $$$0 \le m \le 10^5$$$) — количество вершин в графе и количество ребер в графе.

Во второй строке следуют три целых числа $$$n_1$$$, $$$n_2$$$ и $$$n_3$$$ ($$$0 \le n_1, n_2, n_3 \le n$$$) — необходимое количество цифр 1, 2 и 3, соответственно. Гарантируется, что $$$n_1 + n_2 + n_3 = n$$$.

В следующих $$$m$$$ строках следует описание ребер: в $$$i$$$-й строке следуют два целых числа $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$) — номера вершин, которые соединяет $$$i$$$-е ребро. Гарантируется, что граф не содержит петель и кратных ребер.

Выходные данные

Если существует раскраска, удовлетворяющая всем описанным условиям, выведите в первую строку «YES» (без кавычек). Во вторую строку выведите строку длины $$$n$$$, состоящую только из цифр 1, 2 и 3, причем $$$i$$$-й символ этой строки должен быть равен цифре, которую нужно поставить в $$$i$$$-ю вершину.

Если подходящей раскраски не существует, выведите «NO» (без кавычек).

Примеры
Входные данные
6 3
2 2 2
3 1
5 4
2 5
Выходные данные
YES
112323
Входные данные
5 9
0 2 3
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Выходные данные
NO