Ivan Tsarévitch, en quête de la mort de Kochtcheï l'Immortel, est arrivé dans un bosquet magique. Selon Baba Yaga, il s'y trouve $n$ chênes sages, parmi lesquels exactement $k$ chênes disent toujours la vérité, tandis que les autres mentent toujours.

Pour savoir où aller ensuite, le Tsarévitch doit apprendre des chênes l'itinéraire à suivre. Cependant, il doit être extrêmement prudent, car s'il suit le conseil de l'un des chênes menteurs, il s'égarera dans un marais où le Likho borgne lui tendra une embuscade.

Pour déterminer à quels chênes il peut faire confiance, Ivan a posé à chaque chêne une question sous la forme : « Chêne numéro $i$, dis-moi, le chêne numéro $a_i$ dit-il toujours la vérité ? » Cependant, il ne sait pas comment exploiter les réponses qu'il a reçues.

Aidez Ivan Tsarévitch à tirer des conclusions de ces questions. Pour chaque chêne, déterminez s'il dit toujours la vérité, s'il ment toujours, ou si les informations sont insuffisantes. Si Baba Yaga a trompé Ivan Tsarévitch et qu'il n'existe aucune configuration possible de chênes satisfaisant les données d'entrée, affichez un seul nombre $-2$.

Entrée

La première ligne contient deux entiers $n$ et $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$), désignant respectivement le nombre de chênes et combien d'entre eux disent toujours la vérité.

La $i$-ème des $n$ lignes suivantes contient deux entiers $a_i$ et $b_i$ ($1 \le a_i \le n$, $0 \le b_i \le 1$), indiquant qu'on a demandé au chêne numéro $i$ si le chêne numéro $a_i$ dit toujours la vérité, et que la réponse a été « oui » si $b_i = 1$, ou « non » sinon.

Sortie

Si les données d'entrée sont contradictoires, affichez un seul entier $-2$.

Sinon, affichez $n$ entiers $t_1, t_2, \dots, t_n$ : les conclusions quant à la véracité des chênes. Ils peuvent prendre les valeurs suivantes :

• $t_i = 1$ si le chêne numéro $i$ dit toujours la vérité ;
• $t_i = -1$ si le chêne numéro $i$ ment toujours ;
• $t_i = 0$ s'il est impossible de déterminer à partir des données disponibles si le chêne numéro $i$ ment toujours ou dit toujours la vérité.

Exemples

Entrée 1

6 4
2 0
1 0
3 1
3 0
3 0
6 1

Sortie 1

0 0 -1 1 1 1

Entrée 2

3 1
2 0
3 0
1 0

Sortie 2

-2