There are houses in the city of Waterloo, conveniently numbered from to . These houses are connected by roads (the -th connecting houses and ) such that it is possible to travel between any pair of houses using the roads. As part of an ambitious city renovation plan, each of the roads are to be painted in various colours. A path in this new network is deemed colourful if it contains roads of at least two different colours.
Of course, such a large project must take community needs into account. As such, the colouring of the roads must ensure that there is at least one path between Arid Alice's house and Boring Bob's house that is not colourful. Furthermore, it must also ensure that all paths from Colourful Caiden's house to Diverse Dachi's house are colourful. Any colouring satisfying these conditions is deemed valid.
Either determine that no valid colouring exists, or find any valid colouring that
- Minimizes the total number of colours used (because paint is expensive).
- Ensures that the length of the shortest non-colourful path from to is the minimum possible over all valid colourings.
Each road connects two different houses, and no two roads connect the same pair of houses.
, , , and are pairwise distinct.
Subtask 1 [4/15]
In this subtask, you will get 2/15 points if you correctly determine whether a valid colouring exists in all test cases.
Subtask 2 [11/15]
No additional constraints.
In this subtask,
- You will get 3/15 points if you correctly determine whether a valid colouring exists in all test cases.
- You will get an additional 3/15 points if for all cases where a valid colouring exists, you output a valid colouring that minimizes the total number of colours, but the length of the shortest non-colourful path from to is not the minimum possible over all valid colourings.
The first line contains integers and .
The next lines each contain integers and .
The last line contains integers , , , and .
If no valid colouring exists, output on its own line.
Otherwise, output on the first line, denoting the number of colours used in your solution. For full marks, should be minimized.
Then, on the -th of the next lines, output a single integer , representing the colour of the -th road.
Note that a solution which does not heed the output format provided above will not be rewarded with any points.
Sample Input 1
7 7 1 2 3 1 4 5 7 3 6 5 1 4 3 6 2 7 6 4
Sample Output 1
2 1 1 2 1 1 1 2
Explanation for Sample 1
The colouring of the roads is shown in the diagram above. It can be verified that there is a non-colourful path from to with minimum length over all valid colourings, and that all paths from to are colourful. Note that this is not the only possible solution to this sample case.
Sample Input 2
4 3 1 2 2 3 3 4 1 2 3 4
Sample Output 2