# [Erdős Number (hard)](https://po2punkt0.kattis.com/problems/erdoshard)

## Test group 1: $N\leq10$

This test group can be solved with many different methods.

One way to go about this group is simply to take full advantage of the bound given. Since there can be at most 10 different mathematicians, we could try to solve this problem by looping over all unique mathematicians and "efficiently" determining the minimum distance to Erdős. This can be done by doing a BFS for each mathematician, where each publication represents a separate clique and each mathematician points to every clique it belongs to.

Here is an example of how to implement this in python:

from collections import deque

N, M = map(int, input().split())

belongs_to_group = {}
groups = []
people = set()
for i in range(M):
    data = input().split()
    for pers in data[1:]:
        if pers not in people:
            people.add(pers)
        if pers not in belongs_to_group:
            belongs_to_group[pers] = []
        belongs_to_group[pers].append(i)
    groups.append(data[1:])

dist = {}
for pers in people:
    visited_groups = set()
    queue = deque([(pers, 0)])
    while queue:
        person, d = queue.popleft()
        if person == "ERDOS":
            dist[pers] = d
            queue.clear()
            break
        for i in belongs_to_group[person]: 
            if i in visited_groups:
                continue
            group = groups[i]
            visited_groups.add(i)
            for p in group:
                queue.append((p, d+1))

for name in sorted(dist):
    print(name, dist[name])

This code runs worst case in $O(NS)$, where $S$ is the total amount of mathematicians across all publications, which is guaranteed to be bounded $S\leq3\cdot10^{5}$ and is fast enough for this test group, even in python.

## Full solution

To solve the problem fully we really only need one key insight: Instead of starting the BFS from all N different mathematicians, we could simply start from Erdős and work backwards. This removes the N factor in the time complexity, and we get a code that runs in $O(S)$. Note that we do sort the output at the end, as the problem requires us to do, so in actuality this code runs closer to $O(S+NlogN)$. This is still more than enough to get all 100 points for the full problem.

You could implement this solution like this:

from collections import deque

N, M = map(int, input().split())

belongs_to_group = {}
groups = []
for i in range(M):
    data = input().split()
    for pers in data[1:]:
        if pers not in belongs_to_group:
            belongs_to_group[pers] = []
        belongs_to_group[pers].append(i)
    groups.append(data[1:])

dist = {"ERDOS": 0}
visited_groups = set()
queue = deque(["ERDOS"])

while queue:
    person = queue.popleft()
    for i in belongs_to_group[person]:
        if i in visited_groups:
            continue
        group = groups[i]
        visited_groups.add(i)
        for p in group:
            if p not in dist:
                dist[p] = dist[person] + 1
                queue.append(p)

for name in sorted(dist):
    print(name, dist[name])

An alternate solution was also suggested by the problem setter Harry. The idea is to append a new central node for each clique where the indegree to the mathematicians is 0 and the outdegree is 1. Then you can run a Dijkstra’s algorithm on the graph to determine the shortest path from Erdős to all other mathematicians. This solution runs in roughly $O(S+VlogV)$ where $V=N+M$.

Harry's implementation:

from heapq import heappop, heappush

def dijkstra(graph, start):
    """ 
        Uses Dijkstra's algortihm to find the shortest path from node start
        to all other nodes in a directed weighted graph.
    """
    n = len(graph)
    dist, parents = [float("inf")] * n, [-1] * n
    dist[start] = 0

    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if path_len == dist[v]:
            for w, edge_len in graph[v]:
                if edge_len + path_len < dist[w]:
                    dist[w], parents[w] = edge_len + path_len, v
                    heappush(queue, (edge_len + path_len, w))

    return dist, parents

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

remap = {}

for _ in range(m):
    a = input().split()

    newnode = len(edges)
    edges.append([])
    for name in a[1:]:
        if name not in remap:
            remap[name] = len(remap)
        edges[remap[name]].append((newnode, 0))
        edges[newnode].append((remap[name], 1))

dist, parents = dijkstra(edges, remap["ERDOS"])

reremap = {v: k for k, v in remap.items()}

# Print the authors in alphabetical order
for v, name in sorted(reremap.items(), key=lambda x: x[1]):
    print(name, dist[v])