from collections import deque
import random
import math
import time


# binary/ternary tree.
def graph_add_high_breadth(g, smallest_unused, tmp_root, cnt_new_nodes, cnt_children):
    stop_at = smallest_unused + cnt_new_nodes
    qu, switch_nodes = deque([tmp_root]), []

    while qu:
        nod = qu.popleft()
        added_children = 0
        for j in range(cnt_children):
            if smallest_unused < stop_at:
                g[nod].append(smallest_unused)
                g[smallest_unused].append(nod)
                qu.append(smallest_unused)
                added_children += 1
                smallest_unused += 1

        if added_children < cnt_children:
            switch_nodes.append(nod)

    g[tmp_root] = g[tmp_root][-cnt_children:] + g[tmp_root][:-cnt_children]

    return g, smallest_unused, switch_nodes


# only two levels, most nodes immediately under tmp_root.
def graph_add_high_breadth2(g, smallest_unused, tmp_root, cnt_new_nodes, rap_immediate_new_nodes):
    stop_at = smallest_unused + cnt_new_nodes

    immediate_children, switch_nodes = [], []
    for i in range(int(cnt_new_nodes * rap_immediate_new_nodes)):
        g[tmp_root].append(smallest_unused)
        g[smallest_unused].append(tmp_root)
        immediate_children.append(smallest_unused)
        smallest_unused += 1

    # daca high_breadth e apelat al doilea, vreau sa ca muchiile lui din tmp_root sa fie primele.
    g[tmp_root] = g[tmp_root][-len(immediate_children):] + g[tmp_root][:-len(immediate_children)]

    immediate_children = immediate_children[::-1]
    while smallest_unused < stop_at:
        g[immediate_children[-1]].append(smallest_unused)
        g[smallest_unused].append(immediate_children[-1])
        switch_nodes.append(smallest_unused)
        immediate_children.pop()
        smallest_unused += 1

    return g, smallest_unused, switch_nodes


# cnt_children chains of similar lengths.
def graph_add_high_depth(g, smallest_unused, tmp_root, cnt_new_nodes, cnt_children):
    chain_lengths, add_one_to_first = cnt_new_nodes // cnt_children, cnt_new_nodes % cnt_children
    switch_nodes = []

    for i in range(cnt_children):
        parent = tmp_root
        chain_length = chain_lengths + 1 if i < add_one_to_first else chain_lengths

        for j in range(chain_length):
            g[parent].append(smallest_unused)
            g[smallest_unused].append(parent)
            parent = smallest_unused
            if i + 1 == cnt_children:
                switch_nodes.append(smallest_unused)
            smallest_unused += 1

    return g, smallest_unused, switch_nodes


# two chains, first one is orders of magnitude bigger than the second.
def graph_add_high_depth2(g, smallest_unused, tmp_root, cnt_new_nodes, rap_left_chain):
    chain_lengths = [int(cnt_new_nodes * rap_left_chain), cnt_new_nodes - int(cnt_new_nodes * rap_left_chain)]
    switch_nodes = []

    for ch_id in range(2):
        parent = tmp_root
        for i in range(chain_lengths[ch_id]):
            g[parent].append(smallest_unused)
            g[smallest_unused].append(parent)
            parent = smallest_unused
            if ch_id + 1 == len(chain_lengths):
                switch_nodes.append(smallest_unused)
            smallest_unused += 1

    return g, smallest_unused, switch_nodes


def add_chain_of_length(g, parent, l, smallest_unused):
    for _ in range(l):
        g[parent].append(smallest_unused)
        g[smallest_unused].append(parent)
        parent = smallest_unused
        smallest_unused += 1
    return g, smallest_unused


# https://cp-algorithms.com/graph/pruefer_code.html
def prufer_decode(code: list):
    n = len(code) + 2
    degree = [1 for _ in range(n)]
    for nod in code:
        degree[nod] += 1

    ptr = 0
    while degree[ptr] != 1:
        ptr += 1
    leaf = ptr

    edges = []
    for nod in code:
        edges.append((leaf, nod))
        degree[nod] -= 1
        if degree[nod] == 1 and nod < ptr:
            leaf = nod
        else:
            ptr += 1
            while degree[ptr] != 1:
                ptr += 1
            leaf = ptr

    edges.append((leaf, n-1))
    return edges


def export_test(g, final_node, message):
    with open(f"./gen_100k/{int(time.time() * 100)}_{message}.txt", "w") as fout:
        fout.write(f"{len(g)} {final_node + 1}\n")
        for i in range(len(g)):
            for nn in g[i]:
                if i < nn:
                    fout.write(f"{i+1} {nn+1}\n")