You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

谷米莱莉娅是热心肠的ACM社员。

今天，她听说ACM社的比赛还缺一道字符串题，于是她打算造$n$道字符串题。众所周知，由于字符串题之间往往相似度比较高，于是她还打算用这$n$道题组合再造出$m$道题。具体来说，对于两道字符串题$u,v$，如果它们之间存在一条有向边$(u,v)$，表示题$v$借鉴了题$u$的idea。由于题目之间不可能相互借鉴，所有题和所有边构成了一张有向无环图。记$N=\{1,2,\dots,n\}$，$M=\{n+1,n+2,\dots,m\}$，为了保证题目不缝合太多idea被人怒喷原题，谷米莱莉娅保证对于任意的$u\in M$，$u$最多只借鉴两个ideas。

众所周知，一道题$u$要么是好题，要么是坏题，因此它的价值$val_u$要么为1（好题），要么为0（坏题）。现在，她打算决定前$n$道题的价值，而对于任意的$u\in M$，$val_{u}$由它借鉴的两道题的价值的与非值决定。

由于ACM社的新生赛只缺一道字符串题，她决定将第$n+m$道题交给ACM社，作为最终的字符串题，所以这道题是好题还是坏题至关重要。然而，为了让她出的题具有灵活的米线毒瘤程度，谷米莱莉娅希望她钦点的前$n$道题既能造出好题，又能造出坏题，因此她希望在确定一部分题目$S\sube N$的价值的同时保留另一部分题目$T=N\setminus S$的价值。也就是说，她希望$S$中题目的价值确定，而$T$中题目的价值可以随时更改。

具体来说，记前$n$道题均为好题时$val_{n+m}$为$a$，前$n$道题均为坏题时$val_{n+m}$为$b$。谷米莱莉娅固定$\forall s\in S,val_s$之后，希望当$\forall t\in T,val_t=1$时，$val_{n+m}=a$，而当$\forall t\in T,val_t=0$时，$val_{n+m}=b$。

现在谷米莱莉娅想要造出这样的$n$道题。她想知道她需要如何选取$S$和$T$，以及对于选定的$S$，$S$中题目的价值是什么。除此之外，由于idea有限，她还希望$T$中题目的数量，即$|T|$尽量小。

对两个布尔值$x,y$进行与非的结果$x\overline{\wedge}y\Leftrightarrow\neg(x\wedge y)$。例如，$1\overline{\wedge}0=1,1\overline{\wedge}1=0$。

输入格式

第一行包含一个整数$case$，代表数据组数。

之后每组数据中，第一行包含两个整数$n,m$。

之后的$m$行，每行包含两个不同的整数，第$i$行的两个整数代表第$n+i$道题借鉴的两道题的编号，且它们都小于$n+i$。

输出格式

输出包含$case$行，每行一个长度为$n$的由$0,1,2$构成的字符串，字符串的第$u$位表示$val_u$，特别地，$val_u=0$表示$u\in S$且是坏题，$val_u=1$表示$u\in S$且是好题，$val_u=2$表示$u\in T$。

如果有多个合法解，输出满足$|T|$在所有解中最小的任意一组解即可；如果无解，该行输出$-1$。

样例

1
4 3
1 2
3 4
5 6

0021

数据范围

对于$30\%$的数据，$n,m\le 12$。

对于另外$30\%$的数据，保证图为一棵以点$n+m$为根的，有向边方向自底向上的完全二叉树。

对于另外$10\%$的数据，保证图为一棵以点$n+m$为根的，有向边方向自底向上的二叉树。

对于$100\%$的数据，$1\le case\le 10$，$1\le n,m\le 10^5$。

图中保证没有重边和自环。