Вам задан неориентированный граф без петель и кратных ребер, состоящий из $$$n$$$ вершин и $$$m$$$ ребер. Также вам задано три числа $$$n_1$$$, $$$n_2$$$ и $$$n_3$$$.
Определите, можно ли расставить в вершины графа цифры 1, 2 и 3 так, чтобы выполнялись следующие условия:
Если существует несколько раскрасок, удовлетворяющим все описанным выше условиям, разрешено найти любую из них.
В первой строке следуют два целых числа $$$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
Название |
---|