def read_graph():
    with open('graph_input.txt', 'r') as input_graph:
        j = 0
        all_edges = {}
        for line in input_graph:
            j += 1
            from re import split
            edges = split('\),\(', line)
            max = 0
            for i in range(len(edges)):
                if i != 0:
                    if max < int(edges[i][0]):
                        max = int(edges[i][0])
                    if max < int(edges[i][2]):
                        max = int(edges[i][2])
                else:
                    if max < int(edges[i][1]):
                        max = int(edges[i][1])
                    if max < int(edges[i][3]):
                        max = int(edges[i][3])
            mas = [0] * max
            old = [0] * max
            for i in range(len(edges)):
                if i == 0:
                    edges[i] = edges[i][1:]
                if i == len(edges):
                    edges[i] = edges[i][0:2]
                if i == len(edges) - 1:
                    if edges[i][len(edges[i]) - 1] == '\n':
                        edges[i] = edges[i][:len(edges[i]) - 2]
                    else:
                        edges[i] = edges[i][:len(edges[i]) - 1]
                try:
                    edge = eval(edges[i])
                    if len(edge) != 3 or edge[0] <= 0 or edge[1] <= 0 or edge[2] <= 0:
                        # print('Строка {}: введены неправильные параметры'.format(str(j)))
                        exit()
                except:
                    print('Строка {}: введены неправильные параметры'.format(str(j)))
                    exit()
                if edge[0] not in all_edges:
                    all_edges[edge[0]] = []
                for item in all_edges[edge[0]]:
                    if item[1] == edge[1]:
                        print('Строка {}: введены неправильные параметры, дуга в такую вершину уже существует'.format(
                            str(j)))
                        exit()
                if old[edge[1] - 1] + 1 != edge[2]:
                    print('Строка {}: введены неправильные параметры'.format(str(j)))
                    exit()
                mas[edge[0] - 1] += 1
                old[edge[1] - 1] = edge[2]
                all_edges[edge[0]].append([mas[edge[0] - 1], edge[1]])

                if edge[1] not in all_edges:
                    all_edges[edge[1]] = []

    return all_edges


def transform_graph(all_edges):
    transformed_graph = {}
    last_item = -1
    for item in sorted(all_edges.keys()):
        if last_item == -1:
            if item != 1:
                print('Введены неправильные параметры, первый номер вершины должен быть равен 1')
                exit()
        else:
            if item - last_item != 1:
                print('Введены неправильные параметры, разница между номерам вершин должна равняться 1')
                exit()
        last_item = item
    for vertex in sorted(all_edges.keys()):
        transformed_graph[vertex] = []
        sorted_edges = sorted(all_edges[vertex], key=lambda x: x[0])
        for i in range(len(sorted_edges)):
            if i == 0:
                if sorted_edges[i][0] != 1:
                    print('Введены неправильные параметры, первый порядковый номер дуги должен быть равен 1')
                    exit()
                else:
                    transformed_graph[vertex].append(sorted_edges[i][1])
            else:
                if sorted_edges[i][0] - sorted_edges[i - 1][0] != 1:
                    print('Введены неправильные параметры, разница между порядковыми номерам дуг должна равняться 1')
                    exit()
                else:
                    transformed_graph[vertex].append(sorted_edges[i][1])
    return transformed_graph


def bfs(start, graph, d, p):
    d[start] = 0
    p[start] = start
    queue = [start]
    while len(queue):
        u = queue.pop(0)
        for v in graph[u]:
            if d[v] == 1e30:
                p[v] = u
                d[v] = d[u] + 1
                queue.append(v)
    return d, p


def add_vertex(v, graph, visited, parts):
    visited[v] = True
    add_graph = {v: []}
    for vertex in graph[v]:
        if vertex not in visited:
            add_graph[v].append(add_vertex(vertex, graph, visited, parts))
        else:
            if vertex not in parts:
                add_graph[v].append({vertex: []})
            else:
                add_graph[v].append({vertex: parts[vertex]})
    parts[v] = add_graph[v]
    return add_graph


def construct_graph(graph, d):
    constructed_graph = {}
    sorted_graph = dict(sorted(d.items(), key=lambda x: x[1]))
    parts = {}
    visited = {}
    for item in sorted_graph:
        if sorted_graph[item] == 0:
            add_vertex(item, graph, visited, parts)
            constructed_graph[item] = parts[item]
        else:
            break
    return constructed_graph


def write_to_json(constructed_graph):
    import json
    with open('graph.json', 'w') as outfile:
        json.dump(constructed_graph, outfile, indent=3)


if __name__ == '__main__':
    all_edges = read_graph()
    graph = transform_graph(all_edges)

    d = {}
    p = {}
    for item in sorted(graph.keys()):
        d[item] = 1e30
        p[item] = -1
    for item in sorted(graph.keys()):
        if d[item] == 1e30:
            d, p = bfs(item, graph, d, p)

    constructed_graph = construct_graph(graph, d)
    write_to_json(constructed_graph)