Bob is tinkering with self-driving cars! He realizes that for the cars to drive efficiently, they should not use roads that human drivers are using. Bobland consists of ~N~ cities and ~M~ bidirectional edges. Bob proposes that they find a Triple Spanning Tree within the road system of Bobland to fix this problem. A TST consists of three sets of edges ~E_1~, ~E_2~, and ~E_3~ such that ~E_1 \cap E_2 = \varnothing~, ~E_2 \cap E_3 = \varnothing~ and ~E_3 \cap E_1 = \varnothing~ and it is possible to travel between any two cities in Bobland using only the edges in ~E_1~, using only the edges in ~E_2~, and only the edges in ~E_3~ and the sizes of ~E_1~, ~E_2~, and ~E_3~ are minimal. In other words, ~E_1~, ~E_2~, ~E_3~ are edge-disjoint spanning trees of the graph of Bobland. Help Bob find sets ~E_1~, ~E_2~, ~E_3~ or determine that a TST does not exist in Bobland.

Constraints

In all subtasks,
~2 \le N \le 500~
~1 \le M \le 1\,500~

Subtask 1 [20%]

~1 \le M \le 20~

Subtask 2 [20%]

~2 \le N \le 30~
~1 \le M \le 100~

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, ~N~ and ~M~.
The next ~M~ lines contain two space-separated integers, ~x_i~ and ~y_i~ denoting a bidirectional edge between ~x_i~ and ~y_i~.

Output Specification

If there is no solution, output -1.
Otherwise, output one line consisting of a string of ~M~ characters. The ~i~-th character should be 0 if the ~i~-th edge should belong to none of the sets, 1 if the ~i~-th edge should belong to ~E_1~, 2 if the ~i~-th edge should belong to ~E_2~, and 3 if the ~i~-th edge should belong to ~E_3~. If there are multiple solutions, output any one.

Sample Input 1

4 10
1 2
1 3
2 4
3 4
4 1
3 2
4 2
1 4
2 3
3 1

Sample Output 1

1112223033

Explanation for Sample Output 1

2302112331 would also be a valid solution.

Sample Input 2

5 4
1 2
2 3
1 3
3 1

Sample Output 2

-1

Explanation for Sample Output 2

There is no solution. Note that the graph isn't necessarily connected and could potentially have multiple edges between two nodes.