1144F - Graph Without Long Directed Paths - CodeForces Solution

import threading
import sys

def main():
    n, m = map(int, input().split())

    graph = {}
    visited = [False for _ in range(n)]
    edges = []
    for _ in range(m):
        n1, n2 = map(int, input().split())
        graph[n1] = graph.get(n1, [])
        graph[n2] = graph.get(n2, [])
        graph[n1].append(n2)
        graph[n2].append(n1)
        edges.append((n1, n2))
    color = {1: 1}

    def coloring(node):
        visited[node - 1] = True
        for neighbor in graph[node]:
            if not visited[neighbor - 1]:
                color[neighbor] = 1 if color[node] == 0 else 0
                if not coloring(neighbor):
                    return False
            else:
                if color[neighbor] == color[node]:
                    return False
        return True

    if not coloring(1):
        print("NO")
    else:
        print("YES")
        binary = ""
        for n1, n2 in edges:
            if color[n1] == 1:
                binary += "0"
            else:
                binary += "1"
        print(binary)

if __name__ == '__main__':
    sys.setrecursionlimit(1 << 30)
    threading.stack_size(1 << 27)

    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()