#527. 丘比特的烦恼

丘比特的烦恼

Background

Special for beginners, ^_^

Description

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

Format

Input

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

Output

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

Samples

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

Limitation

N<=200000,M<=600000