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

1. Minimizes the total number of colours used (because paint is expensive).
2. Ensures that the length of the shortest non-colourful path from $A$ to $B$ is the minimum possible over all valid colourings.

Constraints

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

Input Specification

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

Output Specification

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

-1