题目描述

随着社会的不断发展，人与人之间的感情越来越功利化。最近，爱神丘比特发现，爱情也已不再是完全纯洁的了。 这使得丘比特很是苦恼，他越来越难找到合适的男女，并向他们射去丘比特之箭。于是丘比特千里迢迢远赴中国，找到了掌管东方人爱情的神——月下老人，向他求教。

月下老人告诉丘比特，纯洁的爱情并不是不存在，而是他没有找到。 在东方，人们讲究的是缘分。月下老人只要做一男一女两个泥人，在他们之间连上一条红线，那么它们所代表的人就会相爱——无论他们身处何地。

而丘比特的爱情之箭只能射中两个距离相当近的人，选择的范围自然就小了很多，不能找到真正的有缘人。 丘比特听了月下老人的解释，茅塞顿开，回去之后用了人间的最新科技改造了自己的弓箭，使得丘比特之箭的射程大大增加。这样，射中有缘人的机会也增加了不少。

情人节(Valentine's day)的午夜零时，丘比特开始了自己的工作。 他选择了男女各N位，感应到他们互相之间是否有缘分。稍稍思考后，他发现恰好可以发现射出N支神箭，使每个人都找到自己的有缘人。 正当他为自己的发现兴奋不已，准备射箭时，突然想到，自己只感应了是否有缘分，而没考虑缘分的大小。

若是拘泥于射 $n$ 支神箭，却使得某些有天地良缘的不能终成眷属，或勉强把某些只有缘分的男女撮合在一起，便不合自己的本意了。 但是，把每对男女再感应一次太耗时间，于是丘比特只好求助于你了。

Your Task

告诉你他们之间的缘分，请你找出，在射出 $n$ 支神箭的前提下，哪些对有缘人一定会在一起，而哪些对有缘人一定会分开。

输入格式

第一行 $n,m$，表示人数与有缘人的对数。

接下来 $m$ 行，每行 $x,y$ 表示第 $x$ 个男子与第 $y$ 个女子有缘分。

输出格式

按输入顺序，对于每对有缘人输出一个数。

若该对有缘人一定在一起则输出 $1$，若一定分开输出 $2$，否则输出 $0$。

样例输入

3 6
1 1
2 2
3 3
1 2
2 1
3 1

样例输出

001002

数据规模与约定

对于 $100\%$ 的数据，$N \le 200000，M \le 600000$。