DMOPC '19 Contest 3 P6 - TST

View as PDF

Submit solution

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

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 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%]

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


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


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.


There are no comments at the moment.