ANTICHAT — форум по информационной безопасности, OSINT и технологиям

#!/usr/bin/env python
# coding: utf-8
import sys

# чтение входа
N, M, S1, S2 = map(int, sys.stdin.readline().split())
adj = [[] for each in range(N + 1)]  # списки смежности

for each in range(M):
    a, b = map(int, sys.stdin.readline().split())
    adj[a].append(b)
    adj[b].append(a)

olor=dict() # color[x] будет равен цвету вершины

# процедура раскраски графа в два цвета, 0 и 1
def dfs(x, xcolor):
    color[x] = xcolor
    for y in adj[x]:
        if y not in color:  # если y не посетили
            dfs(y, 1 - xcolor)  # посещаем и назначаем противоположный цвет
        elif color[y] !=1- xcolor:  # проверяем на совместимость
            raise 'NO'

try:
  
    dfs(x=1, xcolor=0)

    
    num = [0, 0]
    for x in color.keys():
        num[color[x]] += 1

    
    if (num[0] <= S1 and num[1] <= S2) or (num[0] <= S2 and num[1] <= S1):
        print 'YES'
        if (num[0]<=S1 and num[1]<=S2):
            for x in range(1,N+1) :
                  print color[x]+1,' ',
        else:
            for x in range(1,N+1):
                  print 2-color[x],' ',
        
    else:
        print 'NO'
   
except:
   print 'NO'