Mathematical Trade – Épreuve régionale 2009

Supposez que vous vouliez troquer des objets avec vos amis.

Par exemple, vous avez un ordinateur que vous échangeriez bien contre une peluche géante. Si vous avez un ami qui est d'accord, pas de problème ! Mais que se passe-t-il si votre ami veut échanger votre ordinateur contre un billet d'avion, et qu'un troisième larron veut échanger son billet d'avion contre une peluche géante ? Vous allez devoir faire un échange à trois, tout échange limité à deux personnes devenant impossible.

Cet exercice vise à résoudre ce genre de problèmes, qu'on appelle des "mathematical trades". Des personnes souhaitent échanger des objets (parmi N objets connus). L'on commence par recenser tous les objets en présence. Pour chacun des objets qu'il souhaite échanger, chaque vendeur liste les objets qu'il accepte de recevoir en échange.

L'on vous demande de dire combien d'objets pourront ainsi être échangés au maximum. Il est à noter que le nombre d'objets échangés et les "boucles" d'échanges peuvent devenir assez gros. Ainsi, sur BoardGameGeek.com, qui permet à ses membres d'échanger entre eux des jeux de sociétés, 2320 objets ont été au cours d'une session proposés à l'échange, et 994 ont trouvé preneur, en sept "boucles", dont une géante de 920 objets.

ENTREE

On vous donne le nombre d'objets composant l'échange, suivi du nombre de lignes qui vont suivre. Chaque ligne suivante contient deux entiers. Le premier est le numéro (positif ou nul) de l'objet proposé à l'échange, et le deuxième un objet que le possesseur de l'objet en question est prêt à accepter en échange. Il peut y avoir plusieurs lignes commençant par le même entier (dans le cas où le possesseur est prêt à accepter n'importe quel objet parmi une liste en échange).

SORTIE

Vous devez donner le nombre d'objets échangés au maximum.

CONTRAINTE

N \<= 1000