小红的朋友
题号：NC302599
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红有  个朋友，这些朋友处于两个不同的阵营之中。小红想知道朋友们都处于什么阵营。
为此，小红询问了小苯。小苯依次给出了  条声明，每条声明包含两个整数 ，代表第  人与第  人处于不同的阵营。
不幸的，小苯的声明并不全部正确，且有如下规律：
\hspace{23pt} \bullet 如果一条声明不与之前所有正确的声明产生矛盾，那么这条声明一定是正确的。
\hspace{23pt} \bullet 如果一条声明与之前任意一条正确的声明产生矛盾，那么这条声明一定是错误的。
小红想知道，每条声明分别是正确的还是错误的，请你帮帮他（小苯可能会给出相同的声明）。

输入描述:

第一行输入两个整数 。
之后的  行，每行输入两个整数 x_i,y_i\left(1\leqq x_i,y_i\leqq n ,x_i\ne y_i\right)。

输出描述:

输出一个长为  的  字符串 ，如果  的第  位为 1 则代表第  条声明是正确的，反之则是错误的。
示例1

输入

复制 
3 3
1 2
2 3
1 3

输出

复制 
110

说明

前两条声明不互相矛盾，都为正确，此时第  个朋友和第 3 个朋友一定是同阵营的，第三条声明与之矛盾，是错误的。