We extend the Coupon Collector's Problem (CCP) and present a novel generalized model, referred as the \ekecd problem, where one is interested in recovering a bipartite graph with a perfect matching, which represents the coupons and their matching labels. We show two extra-extensions to this variation: the heterogeneous sample size case (\efmecd) and the partly recovering case.