from typing import Optional, List, Set

class Heap:
    def __init__( self ) -> None:
        self.data : List[ List[ int ] ] = []
        self.refs : List[ int ] = []
        self.marks : List[ bool ] = []

    def boundcheck( self, obj_id: int, index: int ) -> bool:
        return obj_id >= 0 and \
               obj_id < len( self.data ) and \
               index < len( self.data[ obj_id ] )

    def read( self, obj_id: int, index: int ) -> Optional[int]:
        if not self.boundcheck( obj_id, index ):
            return None
        return self.data[ obj_id ][ index ]

    def write( self, obj_id: int, index: int, value: int ) -> bool:
        if not self.boundcheck( obj_id, index ):
            return False
        self.get( value )
        self.put( self.data[ obj_id ][ index ] )
        self.data[ obj_id ][ index ] = value
        return True

    def put( self, obj_id: int ) -> None:
        if obj_id <= 0 or not self.boundcheck( obj_id, 0 ):
            return
        self.refs[ obj_id ] -= 1
        if self.refs[ obj_id ] == 0:
            for val in self.data[ obj_id ]:
                self.put( val )
            self.data[ obj_id ] = []

    def get( self, obj_id: int ) -> None:
        if self.boundcheck( obj_id, 0 ):
            self.refs[ obj_id ] += 1

    def mark( self, now: int ) -> None:
        if not self.boundcheck( now, 0 ) or self.marks[ now ]:
            return
        self.marks[ now ] = True
        for x in self.data[ now ]:
            self.mark( x )

    def collect( self ) -> None:
        self.marks = [ False for _ in self.data ]
        self.mark( 0 )
        for obj_id, live in enumerate( self.marks ):
            if not live:
                self.data[ obj_id ] = []

    def make( self, size: int ) -> int:
        self.data.append( [ 0 for _ in range( size ) ] )
        self.refs.append( 0 )
        return len( self.data ) - 1

import run_tests