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

第一个早晨

作者：顾城

推开门
带上最合法的表情
不要看见别人
也藏好自己的心
煤烟沉沉
再叫我的名字
我不承认

有的人的名字是两个字， 有的人的名字是三个字，还有人的名字是四个字的。现在有两个字的名字的人克制有三个字名字的人，有三个字名字的人克制有四个字名字的人，有四个字名字的人克制有两个字名字的人。
现在有n个人，k个关系，给出每个人名字的长度和两个人之间的克制关系，问这些克制关系是否合法。
第一行两个整数n和k，分别表示人数和关系数。
第二行到第k+1行，每行三个整数opt，a，b，若opt=1，表示第a个人和第b个人名字长度相同，若opt=2，表示第a个人克制第b个人。
一个整数，0或者1
0表示合法
1表示不合法，即存在矛盾情况

输入样例

4 4
1 2 3
1 2 4 
2 1 2
2 1 4

输出样例

0

输入样例

3 3
2 2 1
2 3 2
1 1 3

输出样例

1

数据范围

对于100%的数据，1<=N<=50,000，0<=K<=100,000，保证每个人能名字的长度都只可能为2，3，4，opt只可能为1或者2。