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 cities and
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
,
, and
such that
,
and
and it is possible to travel between any two cities in Bobland using only the edges in
, using only the edges in
, and only the edges in
and the sizes of
,
, and
are minimal. In other words,
,
,
are edge-disjoint spanning trees of the graph of Bobland. Help Bob find sets
,
,
or determine that a TST does not exist in Bobland.
Constraints
In all subtasks,
Subtask 1 [20%]
Subtask 2 [20%]
Subtask 3 [60%]
No additional constraints.
Input Specification
The first line contains two space-separated integers, and
.
The next lines contain two space-separated integers,
and
denoting a bidirectional edge between
and
.
Output Specification
If there is no solution, output -1
.
Otherwise, output one line consisting of a string of characters. The
-th character should be
0
if the -th edge should belong to none of the sets,
1
if the -th edge should belong to
,
2
if the -th edge should belong to
, and
3
if the -th edge should belong to
. 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.
Comments