Énoncé¶
Une autre porte se présente, verrouillée par $N$ serrures. Votre objectif va être de déverrouiller un maximum de serrures simultanément. Cependant, toutes les clés de ces serrures ont été coupée en $P$ morceaux.
Chaque serrure et chaque partie de clé possède un type $i$. Pour ouvrir une serrure, il est donc nécessaire de reformer une clé du même type en rassemblant tous les morceaux correspondants.
Les serrures ainsi que chaque partie de clé sont ordonnées par ordre de type.
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : N, le nombre de serrures.
- Sur la ligne suivante, un entier : P, le nombre de parties nécessaires pour composer une clé.
- Sur la ligne suivante, une liste de N entiers séparés par des espaces : serrures, le type de chaque serrure.
- Sur les lignes suivantes, une liste de P éléments : cles, les
différentes parties des clés.
- Une ligne par élément de la liste : une liste de N entiers séparés par des espaces.
Sortie¶
Afficher, sur une première ligne, le nombre de serrures ouvrables simultanément. Sur une deuxième ligne, afficher, séparés par des espaces, le type de chaque serrure qui peut être ouverte, par ordre croissant de leur type.
Contraintes¶
- $1 \le N \le 1\,000$
- $1 \le P \le 10$
- Il est garanti qu'au moins une serrure peut être ouverte.
- $-1\,000\,000 \le t \le 1\,000\,000$, $t$ étant le type d'une serrure ou d'une partie de clé.
Contraintes de performance¶
- $1 \le P \le 1\,000$