Ivan Tsarevitsj, på leting etter Kosjtsjej den udødeliges død, har kommet til en magisk lund. Ifølge Baba Jaga er det $n$ kloke eiker i den, blant hvilke nøyaktig $k$ eiker alltid snakker sant, mens de andre alltid lyver.
For å finne ut hvor han skal gå videre, må Tsarevitsj få vite den videre ruten fra eikene. Han må imidlertid være ekstremt forsiktig, for hvis han følger rådet fra en av de løgnaktige eikene, vil han vandre inn i en sump der det enøyde Likho ligger i bakhold.
For å finne ut hvilke eiker han kan stole på, har Ivan stilt hver eik et spørsmål på formen: «Eik nummer $i$, fortell meg, snakker eik nummer $a_i$ alltid sant?» Han klarer imidlertid ikke å finne ut hva han skal gjøre med svarene han har mottatt.
Hjelp Ivan Tsarevitsj med å trekke konklusjoner fra spørsmålene. For hver eik, avgjør om den alltid snakker sant, alltid lyver, eller om informasjonen er utilstrekkelig. Hvis Baba Jaga har lurt Ivan Tsarevitsj og det ikke finnes noen mulig konfigurasjon av eiker som tilfredsstiller inndataene, skriv ut ett enkelt tall $-2$.
Inndata
Den første linjen inneholder to heltall $n$ og $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$), som angir henholdsvis antallet eiker og hvor mange av dem som alltid snakker sant.
Den $i$-te av de neste $n$ linjene inneholder to heltall $a_i$ og $b_i$ ($1 \le a_i \le n$, $0 \le b_i \le 1$), som angir at eik nummer $i$ har blitt spurt om eik nummer $a_i$ alltid snakker sant, og at svaret var «ja» hvis $b_i = 1$, eller «nei» ellers.
Utdata
Hvis inndataene er selvmotsigende, skriv ut ett enkelt heltall $-2$.
Ellers, skriv ut $n$ heltall $t_1, t_2, \dots, t_n$: konklusjoner om hvorvidt eikene snakker sant. De kan ha følgende verdier:
- $t_i = 1$ hvis eik nummer $i$ alltid snakker sant;
- $t_i = -1$ hvis eik nummer $i$ alltid lyver;
- $t_i = 0$ hvis det er umulig å avgjøre om eik nummer $i$ alltid lyver eller snakker sant ut fra de tilgjengelige dataene.
Eksempler
Inndata 1
6 4 2 0 1 0 3 1 3 0 3 0 6 1
Utdata 1
0 0 -1 1 1 1
Inndata 2
3 1 2 0 3 0 1 0
Utdata 2
-2