Copillage – Épreuve régionale 2009

On constate lors de la correction du QCM de sélection de nombreuses tricheries : on trouve souvent des codes très proches d'une copie à l'autre.

Quelque fois, des groupes de 3 à 4 personnes se sont même copiées entre elles. Par exemple, si A copie B (ou B copie A, cette relation étant symétrique) et que B copie C, alors on peut dire que A copie C (transitivité).

Au cours de la correction, on note des couples de copies ressemblantes (A,B). On peut alors enregistrer que A a copié B et faire les déductions qui s'imposent.

En parallèle de la correction par les "algorithmiciens" qui notent les copies et donnent au passage les relations de copie, les secrétaires de Prologin assignent les places en demi-finale. Ils veulent pouvoir interroger la base pour savoir si un couple (A,B) est un couple de copieurs (A a copié B) ou non, afin de pouvoir, par exemple, les séparer pendant l'épreuve régionale (quand ils ne les éliminent pas purement et simplement pour copie).

On va donc donner à votre programme une liste de couples (A,B), où A et B sont compris, en valeur absolue, entre 1 et C. Si A et B sont positifs, cela signifie qu'on a détecté que A avait copié B. S'ils sont négatifs, alors on demande si A a copié B. Pour chaque demande, vous devez donner la réponse, 1 ou 0, sur une ligne en sortie, en fonction de ce que vous savez pour le moment (en ignorant donc les relations de copie éventuelles données par les lignes suivantes ; l'idée est qu'il s'agit de deux processus concurrents).

ENTREE

Première ligne : un entier C, le nombre de copies. Deuxième ligne : un entier N, le nombre de couples qui vont suivre. Puis N lignes contenant chacun un couple (A,B) pour une copie détectée ou (-A, -B) (1 \<= A, B \<= C) pour une requête.

LIMITES

C \<= 100 000, N \<= 300 000

SORTIE

Une ligne par requête, "1" si A a copié B et "0" sinon.