定向
题号:NC17449
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

给一张无向图,你需要将边定向,使得定向后的有向图强连通。

输入描述:

第一行两个数n,m,表示点数和边数。
接下来m行,每个两个数x,y,表示x和y之间有条边。

输出描述:

如果不存在可行方案输出一行"impossible" ;

否则,输出一个长度为m的01串,描述你的方案,

第i个字符为1表示输入的第i条边定向为从x到y,为0表示从y到x。
示例1

输入

复制
3 3  
1 2  
1 3  
2 3

输出

复制
101

说明

1->2->3->1,形成一个环 ,是强连通的。

备注:

1 ≤ n,m ≤ 106 ,保证无重边自环