from typing import Counter


def get_valency_structure(graph):
    """Turn graph into a dictionary where the keys are the vertices
    and the values are dictionaries where the keys are again vertices
    and the values are the number of edges shared by those vertices.
    """

    d = {}
    for edge in graph:
        d.setdefault(edge[0], []).append(edge[1])
        d.setdefault(edge[1], []).append(edge[0])
    return {v: Counter(d[v]) for v in d}