Problem p02985 (python)

Fixed submission:
import sys
sys.setrecursionlimit(4100000)

_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = tuple([tuple([int(p) for p in i.split()]) for i in _input[1:n]])

factorial = [0] * (k + 1)
inverse = [0] * (k + 1)
MOD = 1000000007

# Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/175024
def mod_pow1(n, k, mod):
    a = 1
    while k:
        if (k & 1) == 1:
            a = (a * n) % mod
        n = (n * n) % mod
        k >>= 1
    return a

# Ref: https://www.smartbowwow.com/2018/10/mod1097.html
def mod_pow2(n, k, mod):
    if k == 0:
        return 1
    if k % 2 == 0:
        a = mod_pow2(n, k // 2, mod)
        return (a * a) % mod
    else:
        return (n * mod_pow2(n, k - 1, mod)) % mod

#mod_pow = mod_pow1
# It's better to use built-in function for speed.
mod_pow = pow

def mod_factorial_inverse(k, mod):
    factorial[0] = 1
    inverse[0] = 1

    # Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/184011
    for i in range(1, k + 1):
        factorial[i] = ((i * factorial[i - 1]) % mod) # factrial[i]
        inverse[i] = mod_pow(factorial[i], mod - 2, mod) # inverse[i]
 
total = 1

if not edge:
    print(k)
else:
    all_edge = tuple([[] for _ in range(n + 1)])
    for e in edge:
        all_edge[e[0]].append(e[1])
        all_edge[e[1]].append(e[0])
    all_edge = [set(v) for v in all_edge]

    if [v for v in all_edge if len(v) >= k]:
        print(0)
    else:
        mod_factorial_inverse(k, MOD)

        root = edge[0]
        total = (factorial[k] * inverse[k - len(all_edge[root[0]]) - 1]) % MOD

        def dfs(current, from_):
            global total
            child = all_edge[current]
            if len(child) - 1 > 0:
                total = (total * factorial[k - 2] * inverse[k - 2 - (len(child) - 1)]) % MOD
            for c in child:
                if c != from_:
                    dfs(c, current)
        for c in all_edge[root[0]]:
            dfs(c, root[0])
        print(total)

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = tuple([tuple([int(p) for p in i.split()]) for i in _input[1:n]])

factorial = [0] * (k + 1)
inverse = [0] * (k + 1)
MOD = 1000000007

# Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/175024
def mod_pow1(n, k, mod):
    a = 1
    while k:
        if (k & 1) == 1:
            a = (a * n) % mod
        n = (n * n) % mod
        k >>= 1
    return a

# Ref: https://www.smartbowwow.com/2018/10/mod1097.html
def mod_pow2(n, k, mod):
    if k == 0:
        return 1
    if k % 2 == 0:
        a = mod_pow2(n, k // 2, mod)
        return (a * a) % mod
    else:
        return (n * mod_pow2(n, k - 1, mod)) % mod

#mod_pow = mod_pow1
# It's better to use built-in function for speed.
mod_pow = pow

def mod_factorial_inverse(k, mod):
    factorial[0] = 1
    inverse[0] = 1

    # Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/184011
    for i in range(1, k + 1):
        factorial[i] = ((i * factorial[i - 1]) % mod) # factrial[i]
        inverse[i] = mod_pow(factorial[i], mod - 2, mod) # inverse[i]
 
total = 1

if not edge:
    print(k)
else:
    all_edge = tuple([[] for _ in range(n + 1)])
    for e in edge:
        all_edge[e[0]].append(e[1])
        all_edge[e[1]].append(e[0])
    all_edge = [set(v) for v in all_edge]

    if [v for v in all_edge if len(v) >= k]:
        print(0)
    else:
        mod_factorial_inverse(k, MOD)

        root = edge[0]
        total = (factorial[k] * inverse[k - len(all_edge[root[0]]) - 1]) % MOD

        def dfs(current, from_):
            global total
            child = all_edge[current]
            if len(child) - 1 > 0:
                total = (total * factorial[k - 2] * inverse[k - 2 - (len(child) - 1)]) % MOD
            for c in child:
                if c != from_:
                    dfs(c, current)
        for c in all_edge[root[0]]:
            dfs(c, root[0])
        #while len(colored) != n:
        #    current = visit.pop(0)
        #    candidate = all_edge[current] - colored
        #    if candidate:
        #        total = (total * factorial[k - 2] * inverse[k - 2 -len(candidate)]) % MOD
        #        colored.update(candidate)
        #        visit.extend(candidate)
        print(total)

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = tuple([tuple([int(p) for p in i.split()]) for i in _input[1:n]])

import array

factorial = [0] * (k + 1)
inverse = [0] * (k + 1)
MOD = 1000000007

# Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/175024
def mod_pow1(n, k, mod):
    a = 1
    while k:
        if (k & 1) == 1:
            a = (a * n) % mod
        n = (n * n) % mod
        k >>= 1
    return a

# Ref: https://www.smartbowwow.com/2018/10/mod1097.html
def mod_pow2(n, k, mod):
    if k == 0:
        return 1
    if k % 2 == 0:
        a = mod_pow2(n, k // 2, mod)
        return (a * a) % mod
    else:
        return (n * mod_pow2(n, k - 1, mod)) % mod

mod_pow = mod_pow1

def mod_factorial_inverse(k, mod):
    factorial[0] = 1
    inverse[0] = 1

    # Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/184011
    for i in range(1, k + 1):
        factorial[i] = ((i * factorial[i - 1]) % mod) # factrial[i]
        inverse[i] = mod_pow(factorial[i], mod - 2, mod) # inverse[i]
 
if not edge:
    print(k)
else:
    import collections
    import math
 
    all_edge = tuple([[] for _ in range(k + 1)])
    for e in edge:
        all_edge[e[0]].append(e[1])
        all_edge[e[1]].append(e[0])

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = tuple([tuple([int(p) for p in i.split()]) for i in _input[1:n]])

import array

factorial = [0] * (k + 1)
inverse = [0] * (k + 1)
MOD = 1000000007

# Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/175024
def mod_pow1(n, k, mod):
    a = 1
    while k:
        if (k & 1) == 1:
            a = (a * n) % mod
        n = (n * n) % mod
        k >>= 1
    return a

# Ref: https://www.smartbowwow.com/2018/10/mod1097.html
def mod_pow2(n, k, mod):
    if k == 0:
        return 1
    if k % 2 == 0:
        a = mod_pow2(n, k // 2, mod)
        return (a * a) % mod
    else:
        return (n * mod_pow2(n, k - 1, mod)) % mod

mod_pow = mod_pow1

def mod_factorial_inverse(k, mod):
    factorial[0] = 1
    inverse[0] = 1

    # Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/184011
    for i in range(1, k + 1):
        factorial[i] = ((i * factorial[i - 1]) % mod) # factrial[i]
        inverse[i] = mod_pow(factorial[i], mod - 2, mod) # inverse[i]
 
if not edge:
    print(k)
else:
    import collections
    import math
 
    all_edge = tuple([[] for _ in range(k + 1)])
    for e in edge:
        all_edge[e[0]].append(e[1])
        all_edge[e[1]].append(e[0])

    if [v for v in all_edge if len(v) >= k]:
        print(0)
    else:
        mod_factorial_inverse(k, MOD)

        root = edge[0]
        visit  = list(all_edge[root[0]])
        colored = set()
        total = (factorial[k] * inverse[k - len(all_edge[root[0]]) - 1]) % MOD
        colored.add(root[0])
        colored.update(all_edge[root[0]])
        while visit:
            current = visit.pop(0)
            candidate = set(all_edge[current]) - colored
            if candidate:
                total = (total * factorial[k - 2] * inverse[k - 2 -len(candidate)]) % MOD
                colored.update(candidate)
                visit.extend(candidate)

        print(total)

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

if not edge:
    print(k)
else:
    import collections
    import math
    from scipy.special import perm

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

if not edge:
    print(k)
else:
    import collections
    import math
    from scipy.special import perm

    all_edge_map = collections.defaultdict(list)
    for e in edge:
        all_edge_map[e[0]].append(e[1])
        all_edge_map[e[1]].append(e[0])

    if [v for v in all_edge_map if len(all_edge_map[v]) >= k]:
        print(0)
    else:
        root = edge[0]
        visit  = list(all_edge_map[root[0]])
        colored = set()
        math.factorial(k - len(all_edge_map[root[0]]) - 1)
        #total = (math.factorial(k) // math.factorial(k - len(all_edge_map[root[0]]) - 1))
        total = perm(k, len(all_edge_map[root[0]]) + 1, exact=True)
        total %= 1000000007
        colored.add(root[0])
        colored.update(all_edge_map[root[0]])
        while visit:
            current = visit.pop(0)
            candidate = set(all_edge_map[current]) - colored
            if candidate:
                #total *= (math.factorial(k - 2) // math.factorial(k - 2 - len(candidate)))
                total *= perm(k - 2, len(candidate), exact=True)
                total %= 1000000007
                colored.update(candidate)
                visit.extend(candidate)

        print(total)

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

if not edge:
    print(k)
else:
    import collections
    import math
    from scipy.special import perm

    all_edge_map = collections.defaultdict(list)
    for e in edge:
        all_edge_map[e[0]].append(e[1])
        all_edge_map[e[1]].append(e[0])

    if [v for v in all_edge_map if len(all_edge_map[v]) >= k]:
        print(0)
    else:
        root = edge[0]
        visit  = list(all_edge_map[root[0]])
        colored = set()
        math.factorial(k - len(all_edge_map[root[0]]) - 1)
        #total = (math.factorial(k) // math.factorial(k - len(all_edge_map[root[0]]) - 1))
        total = perm(k, len(all_edge_map[root[0]]) + 1)
        total %= 1000000007
        colored.add(root[0])
        colored.update(all_edge_map[root[0]])
        while visit:
            current = visit.pop(0)
            candidate = set(all_edge_map[current]) - colored
            if candidate:
                #total *= (math.factorial(k - 2) // math.factorial(k - 2 - len(candidate)))
                total *= perm(k - 2, len(candidate))
                total %= 1000000007
                colored.update(candidate)
                visit.extend(candidate)

        print(total)

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

if not edge:
    print(k)
else:
    import collections
    import math

    all_edge_map = collections.defaultdict(list)
    for e in edge:
        all_edge_map[e[0]].append(e[1])
        all_edge_map[e[1]].append(e[0])

    if [for v in all_edge_map if len(all_edge_map[v]) >= k]:
        print(0)

    else:
        print('bad')

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

if not edge:
    print(k)
else:
    import collections
    import math

    all_edge_map = collections.defaultdict(list)
    for e in edge:
        all_edge_map[e[0]].append(e[1])
        all_edge_map[e[1]].append(e[0])

    root = edge[0]
    visit  = list(all_edge_map[root[0]])
    tree_edge_map = collections.defaultdict(list)
    colored = []
    math.factorial(k - len(all_edge_map[root[0]]) - 1)
    if (k - len(all_edge_map[root[0]]) - 1) < 0:
        raise

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

if not edge:
    print(k)
else:
    import collections
    import math

    all_edge_map = collections.defaultdict(list)
    for e in edge:
        all_edge_map[e[0]].append(e[1])
        all_edge_map[e[1]].append(e[0])

    root = edge[0]
    visit  = list(all_edge_map[root[0]])
    tree_edge_map = collections.defaultdict(list)
    colored = []
    math.factorial(k - len(all_edge_map[root[0]]) - 1)

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

if not edge:
    print(k)
else:
    import collections
    import math

    all_edge_map = collections.defaultdict(list)
    for e in edge:
        all_edge_map[e[0]].append(e[1])
        all_edge_map[e[1]].append(e[0])

    root = edge[0]
    visit  = list(all_edge_map[root[0]])
    tree_edge_map = collections.defaultdict(list)
    colored = []
    total = (math.factorial(k) // math.factorial(k - len(all_edge_map[root[0]]) - 1))

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

if not edge:
    print(k)
else:
    import collections
    import math

    all_edge_map = collections.defaultdict(list)
    for e in edge:
        all_edge_map[e[0]].append(e[1])
        all_edge_map[e[1]].append(e[0])

    root = edge[0]
    visit  = list(all_edge_map[root[0]])
    tree_edge_map = collections.defaultdict(list)
    colored = []
    total = (math.factorial(k) // math.factorial(k - len(all_edge_map[root[0]]) - 1))
    total %= 1000000007

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

if not edge:
    print(k)
else:
    import collections
    import math

    all_edge_map = collections.defaultdict(list)
    for e in edge:
        all_edge_map[e[0]].append(e[1])
        all_edge_map[e[1]].append(e[0])

    root = edge[0]
    visit  = list(all_edge_map[root[0]])
    tree_edge_map = collections.defaultdict(list)
    colored = []
    total = (math.factorial(k) // math.factorial(k - len(all_edge_map[root[0]]) - 1))
    total %= 1000000007
    colored.append(root[0])
    colored.extend(all_edge_map[root[0]])

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

if not edge:
    print(k)
else:
    import collections
    import math

    all_edge_map = collections.defaultdict(list)
    for e in edge:
        all_edge_map[e[0]].append(e[1])
        all_edge_map[e[1]].append(e[0])

    root = edge[0]
    visit  = list(all_edge_map[root[0]])
    tree_edge_map = collections.defaultdict(list)
    colored = []
    total = (math.factorial(k) // math.factorial(k - len(all_edge_map[root[0]]) - 1))
    total %= 1000000007
    colored.append(root[0])
    colored.extend(all_edge_map[root[0]])
    while visit:
        current = visit.pop(0)
        candidate = [v for v in all_edge_map[current] if v not in colored]
        if candidate:
            total *= (math.factorial(k - 2) // math.factorial(k - 2 - len(candidate)))
            total %= 1000000007
            colored.extend(candidate)
            visit.extend(candidate)

    print(total)

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]
 
import collections
 
colored  = {}
edge_map = collections.defaultdict(list)
for e in edge:
    edge_map[e[0]].append(e[1])
    edge_map[e[1]].append(e[0])
 
root = edge[0][0]

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

import collections

colored  = {}
edge_map = collections.defaultdict(list)
for e in edge:
    edge_map[e[0]].append(e[1])
    edge_map[e[1]].append(e[0])

root = edge[0][0]
colored[root] = k

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

import collections

colored  = {}
edge_map = collections.defaultdict(list)
for e in edge:
    edge_map[e[0]].append(e[1])
    edge_map[e[1]].append(e[0])

root = edge[0][0]
colored[root] = k
for i, p in enumerate(edge_map[root]):
    colored[p] = k - (i + 1)

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

import collections

colored  = {}
edge_map = collections.defaultdict(list)
for e in edge:
    edge_map[e[0]].append(e[1])
    edge_map[e[1]].append(e[0])

root = edge[0][0]
colored[root] = k
for i, p in enumerate(edge_map[root]):
    colored[p] = k - (i + 1)

visit = []
visit.extend(edge_map[root])
while len(colored) != n:
    current = visit.pop(0)
    not_colored = [p for p in edge_map[current] if p not in colored]
    visit = not_colored + visit
    for i, p in enumerate(not_colored):
        colored[p] = k - (i + 2)

total = 1
for i in colored.values():
    total *= i
    if total > 1000000007:
        total %= 1000000007
print(total)

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

import collections

colored  = {}
edge_map = collections.defaultdict(list)
for e in edge:
    edge_map[e[0]].append(e[1])
    edge_map[e[1]].append(e[0])

root = edge[0][0]
colored[root] = k
for i, p in enumerate(edge_map[root]):
    colored[p] = k - (i + 1)

visit = []
visit.extend(edge_map[root])
while visit:
    current = visit.pop(0)
    not_colored = [p for p in edge_map[current] if p not in colored]
    visit = not_colored + visit
    for i, p in enumerate(not_colored):
        colored[p] = k - (i + 2)

total = 1
for i in colored.values():
    total *= i
    if total > 1000000007:
        total %= 1000000007
print(total)

Buggy submission (verdict: Runtime Error):
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

import collections

colored  = {}
edge_map = collections.defaultdict(list)
for e in edge:
    edge_map[e[0]].append(e[1])
    edge_map[e[1]].append(e[0])

root = edge[0][0]
colored[root] = k
for i, p in enumerate(edge_map[root]):
    colored[p] = k - (i + 1)

visit = []
visit.extend(edge_map[root])
while visit:
    current = visit.pop(0)
    not_colored = [p for p in edge_map[current] if p not in colored]
    visit = not_colored + visit
    for i, p in enumerate(not_colored):
        colored[p] = k - (i + 2)

print(colored)
total = 1
for i in colored.values():
    total *= i
    if total > 1000000007:
        total %= 1000000007
print(total)