Problem:


社員旅行

Problem Statement

あなたの会社にはn人の社員が存在する．m個の社員(a_i,b_i)の組について，a_iはb_iの上司である．

社員xが社員yの実質的な上司であるとは，次のうち少なくとも一方が成り立つことをいう．

xがyの上司である．

yの実質的な上司である社員zが存在して，xはzの上司である．

あなたの会社で，自分自身が自分の実質的な上司であるような社員は存在しない．

あなたの会社では社員が全員参加する社員旅行が計画されている．全社員の要求により，旅館での部屋割りは「よい部屋割り」でなければならない．

ある部屋割りが「よい部屋割り」であるとは以下の両方が満たされることをいう．

各社員はどこかの部屋に割り振られる．

社員xと社員yが同じ部屋に割り振られているとき，xはyの実質的な上司でない．

幹事の社員は非常に優秀なので，「よい部屋割り」でかつ必要な部屋の数が最小になるように部屋割りを行った．しかし残念なことに予算が不足している．どうしても必要な部屋の数を減らさなければならないらしい．

そこで，人事部で働くあなたは上司-部下の関係を一つだけ解消することによって，「よい部屋割り」を得るために必要な部屋の数を減らすことにした．

さて，どの関係を解消すればよいのだろう？

Input

入力は以下の形式に従う．与えられる数は全て整数である．

n m
a_1 b_1
...
a_m b_m

Constraints

2≦n≦10^5

1≦m≦2 \times 10^5

1≦a_i<b_i≦n

i \neq jならば(a_i, b_i) \neq (a_j, b_j)

Output

次を満たすようなiを昇順に1行ずつ出力せよ．

「a_iがb_iの上司である」という関係を解消したとき，「よい部屋割り」を得るために必要な部屋の数を減らすことができる．

そのようなiが存在しない場合は-1を1行に出力せよ．

Sample Input 1

5 4
1 2
2 3
3 4
3 5

Output for the Sample Input 1

1
2



Sample input:
5 4
1 2
2 3
3 4
3 5


Sample output:
1
2

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(100000)


def memoize(f):
    cache = {}

    def helper(arg):
        if arg not in cache:
            cache[arg] = f(arg)
        return cache[arg]

    return helper


def solve(edges):
    @memoize
    def tree_height(node):
        en = edges[node]
        if not en:
            return 0, set()
        max_depth = -1
        max_bridges = None
        for edge in en:
            depth, bridges = tree_height(edge[0])
            if depth > max_depth:
                max_depth = depth
                max_bridges = bridges.copy()
                max_bridges.add(edge[1])
            elif depth == max_depth:
                max_bridges.intersection_update(bridges)
        return max_depth + 1, max_bridges

    removable = tree_height(0)[1]
    print('\n'.join(map(str, sorted(removable)[1:])) if len(removable) > 1 else -1)


n, m = map(int, input().split())
root_flags = [False] + [True] * n
edges = [set() for _ in range(n + 1)]

for i in range(m):
    a, b = map(int, input().split())
    edges[a].add((b, i + 1))
    root_flags[b] = False

edges[0] = set((i, -1) for i, f in enumerate(root_flags) if f)

solve(edges)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

n, m = map(int, input().split())
root_flags = [True] * n
edges = [set() for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    edges[a].add((b, i + 1))
    root_flags[b] = False

roots = set(i for i, f in enumerate(root_flags) if f)


def solve():
    def tree_height(node):
        en = edges[node]
        return 0 if not en else max(tree_height(edge[0]) for edge in en) + 1

    heights = sorted((tree_height(root), root) for root in roots)
    if len(heights) > 1 and heights[-2][0] == heights[-1][0]:
        print(-1)
        return
    depth, root = heights[-1]
    queue = [(t, (i,)) for t, i in edges[root]]
    deepest_path = set()
    while queue:
        node, path = queue.pop()
        if len(path) == depth:
            deepest_path.add(path)
            continue
        queue.extend((t, path + (i,)) for t, i in edges[node])

    print('\n'.join(map(str, sorted(reduce(lambda r, c: r & c, map(set, deepest_path))))))


solve()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce


def hierarchize(n, f_edges, b_edges):
    heights = [0] * n
    height = 1
    nodes = {edge[0] for i in range(n) if not f_edges[i] for edge in b_edges[i]}
    while nodes:
        for i in nodes:
            heights[i] = height
        nodes = {edge[0] for i in nodes for edge in b_edges[i]}
        height += 1

    node_hierarchy = [set() for _ in range(max(heights) + 1)]
    for i in range(n):
        node_hierarchy[heights[i]].add(i)

    return node_hierarchy


n, m = map(int, input().split())
f_edges = [set() for _ in range(n)]
b_edges = [set() for _ in range(n)]

for i in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    f_edges[a].add((b, i + 1))
    b_edges[b].add((a, i + 1))

hierarchy = hierarchize(n, f_edges, b_edges)

prev = {}

for h, nodes in enumerate(hierarchy):
    current = {}
    for i in nodes:
        max_bridges = set()
        for edge in f_edges[i]:
            if not edge[0] in prev:
                continue
            if not max_bridges:
                max_bridges = prev[edge[0]].copy()
                max_bridges.add(edge[1])
            else:
                max_bridges &= prev[edge[0]]
        current[i] = max_bridges
    prev = current

result = sorted(reduce(lambda r, c: r & c, prev.values()))
print('\n'.join(map(str, result)) if result else -1)

Submission status: Memory Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)


def memoize(f):
    cache = {}

    def helper(arg):
        if arg not in cache:
            cache[arg] = f(arg)
        return cache[arg]

    return helper


def solve(edges):
    @memoize
    def tree_height(node):
        en = edges[node]
        if not en:
            return 0, set()
        max_depth = -1
        max_bridges = None
        for edge in en:
            depth, bridges = tree_height(edge[0])
            if depth > max_depth:
                max_depth = depth
                max_bridges = bridges.copy()
                max_bridges.add(edge[1])
            elif depth == max_depth:
                max_bridges.intersection_update(bridges)
        return max_depth + 1, max_bridges

    removable = sorted(filter(lambda x: x > 0, tree_height(0)[1]))
    print('\n'.join(map(str, removable)) if removable else -1)


n, m = map(int, input().split())
root_flags = [False] + [True] * n
edges = [set() for _ in range(n + 1)]

for i in range(m):
    a, b = map(int, input().split())
    edges[a].add((b, i + 1))
    root_flags[b] = False

edges[0] = set((i, -1) for i, f in enumerate(root_flags) if f)

solve(edges)

Submission status: Memory Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)


def memoize(f):
    cache = [None] * (n + 1)

    def helper(arg):
        if cache[arg] is None:
            cache[arg] = f(arg)
        return cache[arg]

    return helper


def solve(edges):
    @memoize
    def tree_height(node):
        en = edges[node]
        if not en:
            return 0, set()
        max_depth = -1
        max_bridges = None
        for edge in en:
            depth, bridges = tree_height(edge[0])
            if depth > max_depth:
                max_depth = depth
                max_bridges = bridges.copy()
                max_bridges.add(edge[1])
            elif depth == max_depth:
                max_bridges &= bridges
        return max_depth + 1, max_bridges

    removable = sorted(filter(lambda x: x > 0, tree_height(0)[1]))
    print('\n'.join(map(str, removable)) if removable else -1)


n, m = map(int, input().split())
root_flags = [False] + [True] * n
edges = [set() for _ in range(n + 1)]

for i in range(m):
    a, b = map(int, input().split())
    edges[a].add((b, i + 1))
    root_flags[b] = False

edges[0] = set((i, -1) for i, f in enumerate(root_flags) if f)

solve(edges)

Submission status: Memory Limit Exceeded

Solution code:
from functools import reduce


def hierarchize(n, f_edges, b_edges):
    heights = [0] * n
    height = 1
    nodes = {edge[0] for i in range(n) if not f_edges[i] for edge in b_edges[i]}
    while nodes:
        for i in nodes:
            heights[i] = height
        nodes = {edge[0] for i in nodes for edge in b_edges[i]}
        height += 1

    node_hierarchy = [set() for _ in range(max(heights) + 1)]
    for i in range(n):
        node_hierarchy[heights[i]].add(i)

    return node_hierarchy


n, m = map(int, input().split())
f_edges = [set() for _ in range(n)]
b_edges = [set() for _ in range(n)]

for i in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    f_edges[a].add((b, i + 1))
    b_edges[b].add((a, i + 1))

hierarchy = hierarchize(n, f_edges, b_edges)
max_height = len(hierarchy) - 1

results = [None for _ in range(n)]

for h, nodes in enumerate(hierarchy):
    for i in nodes:
        max_bridges = set()
        for edge in f_edges[i]:
            height, bridges = results[edge[0]]
            if height == h - 1:
                if not max_bridges:
                    max_bridges = bridges.copy()
                    max_bridges.add(edge[1])
                else:
                    max_bridges &= bridges
        results[i] = (h, max_bridges)

result = sorted(reduce(lambda r, c: r & c, (d[1] for d in results if d[0] == max_height)))
print('\n'.join(map(str, result)) if result else -1)

Submission status: Runtime Error

Solution code:
def memoize(f):
    cache = {}

    def helper(arg):
        if arg not in cache:
            cache[arg] = f(arg)
        return cache[arg]

    return helper


def solve(edges):
    @memoize
    def tree_height(node):
        en = edges[node]
        if not en:
            return 0, set()
        max_depth = -1
        max_bridges = None
        for edge in en:
            depth, bridges = tree_height(edge[0])
            if depth > max_depth:
                max_depth = depth
                max_bridges = bridges.copy()
                max_bridges.add(edge[1])
            elif depth == max_depth:
                max_bridges.intersection_update(bridges)
        return max_depth + 1, max_bridges

    removable = tree_height(0)[1]
    print('\n'.join(map(str, sorted(removable)[1:])) if len(removable) > 1 else -1)


n, m = map(int, input().split())
root_flags = [False] + [True] * n
edges = [set() for _ in range(n + 1)]

for i in range(m):
    a, b = map(int, input().split())
    edges[a].add((b, i + 1))
    root_flags[b] = False

edges[0] = set((i, -1) for i, f in enumerate(root_flags) if f)

solve(edges)