## DMOPC '19 Contest 3 P6 - TST

View as PDF

Points: 25
Time limit: 0.75s
Memory limit: 64M

Author:
Problem type

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.

#### 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.