#P18016. Ivan Tsarevich in the Magical Grove

Ivan Tsarevich in the Magical Grove

Ivan Tsarevich in the Magical Grove

一片树林中有 nn 棵会说话的橡树,其中恰好 kk 棵永远说真话,其余永远说假话。

Ivan 对每棵树 ii 都问了一个问题:“树 aia_i 是否永远说真话?”树 ii 的回答用 bib_i 表示:bi=1b_i=1 表示“是”,bi=0b_i=0 表示“否”。树可能被问及自己。

请根据所有回答及恰好 kk 棵树说真话这一条件,判断每棵树是否一定说真话、一定说假话,或仍无法确定。如果不存在符合全部条件的真假分配,输出 −2-2。

输入格式

第一行两个整数 n,kn,k。接下来 nn 行,第 ii 行两个整数 ai,bia_i,b_i,描述树 ii 的回答。

输出格式

若条件矛盾,输出一行一个整数 -2。

否则输出 nn 个整数 t1,…,tnt_1,\ldots,t_n:

  • ti=1t_i=1:在所有符合条件的分配中,树 ii 都说真话;
  • ti=−1t_i=-1:在所有符合条件的分配中,树 ii 都说假话;
  • ti=0t_i=0:两种情况都有可能,无法确定。

数据范围

1≤n≤5×1051\le n\le5\times10^5,0≤k≤n0\le k\le n,1≤ai≤n1\le a_i\le n,bi∈{0,1}b_i\in\{0,1\}。

样例 1

输入

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

输出

0 0 -1 1 1 1

样例 2

输入

3 1
2 0
3 0
1 0

输出

-2