传统题 1000ms 256MiB

听说我们缺字符串题

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

众所周知,一道题uu要么是好题,要么是坏题,因此它的价值valuval_u要么为1(好题),要么为0(坏题)。现在,她打算决定前nn道题的价值,而对于任意的uMu\in Mvaluval_{u}由它借鉴的两道题的价值的与非值决定。

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

具体来说,记前nn道题均为好题时valn+mval_{n+m}aa,前nn道题均为坏题时valn+mval_{n+m}bb。谷米莱莉娅固定sS,vals\forall s\in S,val_s之后,希望当tT,valt=1\forall t\in T,val_t=1时,valn+m=aval_{n+m}=a,而当tT,valt=0\forall t\in T,val_t=0时,valn+m=bval_{n+m}=b

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

对两个布尔值x,yx,y进行与非的结果xy¬(xy)x\overline{\wedge}y\Leftrightarrow\neg(x\wedge y)。例如,10=1,11=01\overline{\wedge}0=1,1\overline{\wedge}1=0

输入格式

第一行包含一个整数casecase,代表数据组数。

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

之后的mm行,每行包含两个不同的整数,第ii行的两个整数代表第n+in+i道题借鉴的两道题的编号,且它们都小于n+in+i

输出格式

输出包含casecase行,每行一个长度为nn的由0,1,20,1,2构成的字符串,字符串的第uu位表示valuval_u,特别地,valu=0val_u=0表示uSu\in S且是坏题,valu=1val_u=1表示uSu\in S且是好题,valu=2val_u=2表示uTu\in T

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

样例

1
4 3
1 2
3 4
5 6
0021

数据范围

对于30%30\%的数据,n,m12n,m\le 12

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

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

对于100%100\%的数据,1case101\le case\le 101n,m1051\le n,m\le 10^5

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

“ASFR” Cup 2nd

未参加
状态
已结束
规则
IOI
题目
13
开始于
2023-10-14 0:00
结束于
2023-10-16 0:00
持续时间
48 小时
主持人
参赛人数
162