Description

随着社会的不断发展，人与人之间的感情越来越功利化。最近，爱神丘比特发现，爱情也已不再是完全纯洁的了。这使得丘比特很是苦恼，他越来越难找到合适的男女，并向他们射去丘比特之箭。于是丘比特千里迢迢远赴中国，找到了掌管东方人爱情的神——月下老人，向他求教。月下老人告诉丘比特，纯洁的爱情并不是不存在，而是他没有找到。在东方，人们讲究的是缘分。月下老人只要做一男一女两个泥人，在他们之间连上一条红线，那么它们所代表的人就会相爱——无论他们身处何地。而丘比特的爱情之箭只能射中两个距离相当近的人，选择的范围自然就小了很多，不能找到真正的有缘人。丘比特听了月下老人的解释，茅塞顿开，回去之后用了人间的最新科技改造了自己的弓箭，使得丘比特之箭的射程大大增加。这样，射中有缘人的机会也增加了不少。情人节(Valentine's day)的午夜零时，丘比特开始了自己的工作。他选择了男女各N位，感应到他们互相之间是否有缘分。稍稍思考后，他发现恰好可以发现射出N支神箭，使每个人都找到自己的有缘人。正当他为自己的发现兴奋不已，准备射箭时，突然想到，自己只感应了是否有缘分，而没考虑缘分的大小。若是拘泥于射N支神箭，却使得某些有天地良缘的不能终成眷属，或勉强把某些只有猿粪的男女撮合在一起，便不合自己的本意了。但是，把每对男女再感应一次太耗时间，于是丘比特只好求助于你了。 Your Task 告诉你他们之间的缘分，请你找出，在射出N支神箭的前提下，哪些对有缘人一定会在一起，而哪些对有缘人一定会分开。

Input

第一行N M，表示人数与有缘人的对数接下来M行，每行X Y表示第X个男子与第Y个女子有缘分 N<=200000，M<=600000

Output

按输入顺序，对于每对有缘人输出一个数若该对有缘人一定在一起则输出1，若一定分开输出2，否则输出0

Sample Input

Sample Output

Hint

Source