There are ~N~ houses in the city of Waterloo, conveniently numbered from ~1~ to ~N~. These houses are connected by ~M~ roads (the ~i~-th connecting houses ~a_i~ and ~b_i~) 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 ~M~ 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 ~A~ and Boring Bob's house ~B~ that is not colourful. Furthermore, it must also ensure that all paths from Colourful Caiden's house ~C~ to Diverse Dachi's house ~D~ 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 ~A~ to ~B~ is the minimum possible over all valid colourings.
~4 \le N \le 2 \times 10^5~
~3 \le M \le 2 \times 10^5~
~1 \le a_i, b_i \le N~
Each road connects two different houses, and no two roads connect the same pair of houses.
~1 \le A, B, C, D \le N~
~A~, ~B~, ~C~, and ~D~ are pairwise distinct.
Subtask 1 [4/15]
~M = N - 1~
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 ~A~ to ~B~ is not the minimum possible over all valid colourings.
The first line contains ~2~ integers ~N~ and ~M~.
The next ~M~ lines each contain ~2~ integers ~a_i~ and ~b_i~.
The last line contains ~4~ integers ~A~, ~B~, ~C~, and ~D~.
If no valid colouring exists, output ~-1~ on its own line.
Otherwise, output ~K~ ~(1 \le K \le 10^9)~ on the first line, denoting the number of colours used in your solution. For full marks, ~K~ should be minimized.
Then, on the ~i~-th of the next ~M~ lines, output a single integer ~c_i~ ~(1 \le c_i \le K)~, representing the colour of the ~i~-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 ~A~ to ~B~ with minimum length over all valid colourings, and that all paths from ~C~ to ~D~ 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