現在有 \(n\) 個島嶼和 \(m\) 座橋，每條座橋連接兩個島嶼，每座島嶼上各有一個外賣員和一個客人。

定義 \(d(u,v)\) 為在島嶼 \(u\) 的外賣員要走到島嶼 \(v\) 送外賣給該島的客人，最多可以走過的橋數，其中同一座橋不能走過兩遍。特別的，如果不可能走到的話，\(d(u,v)=0\)。

換句話說，如果能從島嶼 \(u\) 走到島嶼 \(v\)，則 \(d(u,v)\) 為同一條邊不經過兩次以上的條件下，島嶼 \(u\) 到島嶼 \(v\) 的最遠距離。

作為一個大壞蛋，你的任務是固定每座橋的方向，使得 \(\sum_{i=1}^n \sum_{j=1}^n d(i,j)=m\)。

請完成你的任務，如果找不到方法，也請回報不可能。

Input

第一行輸入兩個正整數 \(n,m\)。

\(2\le n\le 10^5,1\le m\le \min(\frac{n(n-1)}{2},5\cdot 10^5)\)

接下來輸入 \(m\) 行，第 \(i\) 行輸入兩個數 \(u_i,v_i\)，代表第 \(i\) 座橋的兩個端點島嶼。

對於所有 \(1\le i\le m\)，\(u_i\neq v_i\) 且 \(1\le u_i,v_i\le n\)

對於所有 \(i\neq j\)，\(\{u_i,v_i\}\neq \{u_j,v_j\}\)

Output

如果不存在固定橋方向的方法使得 \(\sum_{i=1}^n \sum_{j=1}^n d(i,j)=m\)，則請輸出 \(-1\)

否則請輸出一個長度是 \(m\) 的字串 \(s\) 代表固定橋方向的方法，其中第 \(i\) 個字元 \(s_i\) 必須是 \(0\) 或 \(1\)。

若 \(s_i=0\) 則表示第 \(i\) 座橋固定方向後只能從 \(u_i\) 走到 \(v_i\)。

若 \(s_i=1\) 則表示第 \(i\) 座橋固定方向後只能從 \(v_i\) 走到 \(u_i\)。

如果有多種可行的方法，請輸出 字典序最小的方法。

Constraints

第 \(1\) 組測資, \(n,m\le 20\)。\((23\text{%})\)

第 \(2\) 組測資, \(m=n-1\) 且一開始所有島嶼是連通的。\((30\text{%})\)

第 \(3\) 組測資, 沒有其他限制。\((47\text{%})\)

Sample Input 1

6 5
2 1
1 5
1 4
6 1
3 1

Sample Output 1

01100

Sample Input 2

8 9
8 1
1 2
1 5
2 6
6 5
6 4
4 7
7 3
3 5

Sample Output 2

-1