Problem 5761. -- 深黑幻想

5761: 深黑幻想

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board]

Description

凡终于发愤图强,决定专心搞OI,不再玩纸牌和坑钱了!没过多久就飘飘然了,总是陷入自己进了集训队的深黑幻想之中。
样听说了之后,决定考一考凡欧拉回路怎么写。
样:"我给你出一道题啊,是欧拉回路的,有N个点……"
凡:"欧拉回路有什么卵用?你看Epacs不会写也能进集训队!"
样:"他不会写欧拉回路,但他会做题啊,比如说这道题……
"有N个点,M条奇怪的单向边,每个边有三个参数Ai,Bi,Ci,你可以指定这条边是从Ai连向Bi还是从Ai连向Ci,
要求你构造一种方案使得把这M条边都指定完了之后,每个点的出度和入度相等!"
凡:"这题我会做啊,但是这tmd和欧拉回路有什么关系?!"

Input

第一行两个正整数N,M,表示点的数目与边的数目
接下来M行,每行三个正整数,代表Ai,Bi,Ci,含义如题目中所示

Output

输出一个长度为M的由01组成的字符串代表一个合法解
其中第i个位置为0代表Ai向Bi连边,为1代表Ai向Ci连边
如果有多组解,输出任意一组即可,保证存在合法解
N,M≤ 50000
保证所有的Ci=Bi+1
对于所有数据,保证1<=Ai,Bi,Ci<=N,但是不保证Ai,Bi,Ci互不相同。

Sample Input

3 2
1 2 3
2 1 3

Sample Output

00

HINT

请不要提交!

Source

[Submit][Status]