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.
In all subtasks,
~2 \le N \le 500~
~1 \le M \le 1\,500~
Subtask 1 [20% of points]
~1 \le M \le 20~
Subtask 2 [20% of points]
~2 \le N \le 30~
~1 \le M \le 100~
Subtask 3 [60% of points]
No additional constraints.
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~.
If there is no solution, output
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.
4 10 1 2 1 3 2 4 3 4 4 1 3 2 4 2 1 4 2 3 3 1
Explanation for Sample Output
2302112331 would also be a valid solution.
Sample Input 2
5 4 1 2 2 3 1 3 3 1
Sample Output 2
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.