AttributeError when using python deepcopy

I have a class that has __eq__ and __hash__ overridden, to make its objects act as dictionary keys. Each object also carries a dictionary, keyed by other objects of the same class. I get a weird AttributeError when I try to deepcopy the whole structure. I am using Python 3.6.0 on OsX.

From Python docs it looks as if deepcopy uses a memo dictionary to cache the objects it has already copied, so nested structures should not be a problem. What am I doing wrong then? Should I code up my own __deepcopy__ method to work around this? How?

from copy import deepcopy


class Node:

    def __init__(self, p_id):
        self.id = p_id
        self.edge_dict = {}
        self.degree = 0

    def __eq__(self, other):
        return self.id == other.id

    def __hash__(self):
        return hash(self.id)

    def add_edge(self, p_node, p_data):
        if p_node not in self.edge_dict:
            self.edge_dict[p_node] = p_data
            self.degree += 1
            return True
        else:
            return False

if __name__ == '__main__':
    node1 = Node(1)
    node2 = Node(2)
    node1.add_edge(node2, "1->2")
    node2.add_edge(node1, "2->1")
    node1_copy = deepcopy(node1)

File ".../node_test.py", line 15, in __hash__
    return hash(self.id)
AttributeError: 'Node' object has no attribute 'id'