做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2517. -- 深黑幻想

2517: 深黑幻想

时间限制: 1 Sec  内存限制: 256 MB
提交: 3  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

凡终于发愤图强,决定专心搞 OI,不再玩纸牌和坑钱了!没过多久就飘飘然了,总是陷入自己进了集训队的深黑幻想之中。

样听说了之后,决定考一考凡欧拉回路怎么写。

样:“我给你出一道题啊,是欧拉回路的,有 NNN 个点......”。

凡:“欧拉回路有什么卵用?你看 Epacs 不会写也能进集训队!”。

样:“他不会写欧拉回路,但他会做题啊,比如说这道题......”。

“有 NNN 个点,MMM 条奇怪的单向边,每个边有三个参数 AiA_iAiBiB_iBiCiC_iCi,你可以指定这条边是从 AiA_iAi 连向 BiB_iBi 还是从 AiA_iAi 连向 CiC_iCi,要求你构造一种方案使得把这 MMM 条边都指定完了之后,每个点的出度和入度相等!”。

凡:“这题我会做啊,但是这 tmd 和欧拉回路有什么关系?!”

输入

第一行两个正整数 NNNMMM,表示点的数目与边的数目。

接下来 MMM 行,每行三个正整数,代表 AiA_iAiBiB_iBiCiC_iCi,含义如题目中所示。

输出

输出一个长度为 MMM 的由 010101 组成的字符串代表一个合法解。

其中第 iii 个位置为 000 代表 AiA_iAiBiB_iBi 连边,为 111 代表 AiA_iAiCiC_iCi 连边。

如果有多组解,输出任意一组即可,保证存在合法解。

样例输入

3 2
1 2 3
2 1 3

样例输出

00

提示

特殊性质 1: 保证所有的 Ci=Bi+1C_i=B_i+1Ci=Bi+1

对于所有数据,保证 1Ai,Bi,CiN1\le A_i,B_i,C_i\le N1Ai,Bi,CiN,但是不保证 AiA_iAiBiB_iBiCiC_iCi 互不相同

标签

[上一题][提交][讨论版][状态][下一题]