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.
Constraints
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.
Input Specification
The first line contains integers
and
.
The next lines each contain
integers
and
.
The last line contains integers
,
,
, and
.
Output Specification
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
-1
Comments