B. Saki and Sewage System
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Saki would like to install sewage system in two villages $$$A$$$ and $$$B$$$, each containing $$$N$$$ houses numbered from $$$0$$$ to $$$N-1$$$. For each village, the house numbered $$$0$$$ is located at the highest altitude, while the house numbered $$$N-1$$$ is located at the lowest altitude.

Saki will order $$$2$$$ pipes for each of the $$$M$$$ types of pipes, for the total of $$$2M$$$ pipes. Saki will install $$$M$$$ pipes of different types to each village.

Each pipe has a fixed non-negative integer capacity, and connects two different houses of the same village. Two pipes of the same type have the same capacity. Note that some pipe may have zero capacity (such pipes are for cosmetic purposes). It is already determined which pipe connects which houses, but the capacities have not yet been determined.

After installation, the maximum flow of water in each village is defined as the maximum flow from $$$0$$$ to $$$N-1$$$ when the given sewage system is interpreted as an undirected flow network.

As the village $$$B$$$ has a bigger population than $$$A$$$, Saki would like the maximum flow of water of village $$$B$$$ to be strictly greater than that of $$$A$$$. She can ask pipemakers to set the capacity of each type of pipe to any non-negative integer she wants, but she hasn't decided on the values.

Write a program to help Saki determine if it is possible to assign non-negative integer capacity to each pipe so that the maximum flow of water of village $$$B$$$ is strictly greater than that of $$$A$$$, and if possible, show one possible way to assign capacities.

Input

The input is given in the following format:

$$$N$$$$$$M$$$
$$$U_0$$$$$$V_0$$$
$$$U_1$$$$$$V_1$$$
$$$\vdots$$$
$$$U_{M-1}$$$$$$V_{M-1}$$$
$$$X_0$$$$$$Y_0$$$
$$$X_1$$$$$$Y_1$$$
$$$\vdots$$$
$$$X_{M-1}$$$$$$Y_{M-1}$$$

where $$$N$$$ is the number of houses on each villages, $$$M$$$ is the number of types of pipes, and the pipe of type $$$i$$$ connects $$$U_i$$$ and $$$V_i$$$ on village $$$A$$$, and $$$X_i$$$ and $$$Y_i$$$ on village $$$B$$$.

The input satisfies the following constraints:

  • All numbers in the input are integers.
  • $$$2 \le N \le 20$$$
  • $$$1 \le M \le 200$$$
  • $$$0 \le U_i, V_i, X_i, Y_i \lt N$$$, $$$U_i \ne V_i$$$, and $$$X_i \ne Y_i$$$ for all integer $$$0 \le i \lt M$$$.

Note that the same pair of houses can be connected by multiple pipes.

Output

If there is no assignment of capacities such that the maximum flow of water of the village $$$B$$$ is strictly greater than that of $$$A$$$, print a single line containing $$$-1$$$. Otherwise, the output should be in the following format:

$$$C_0$$$$$$C_1$$$$$$\cdots$$$$$$C_{M-1}$$$

where $$$C_i$$$ is the capacity of the edge of type $$$i$$$.

In such case, the output should satisfy the following constraints:

  • All numbers in the output are integers.
  • $$$0 \le C_i \lt 100\,000$$$ for all integer $$$0 \le i \lt M$$$

It can be proved that if a desired assignment of non-negative integer capacities exists, there also exists a desired assignment satisfying the above constraints.

Examples
Input
4 3
0 3
0 3
0 3
0 1
0 2
0 3
Output
-1
Input
4 3
0 1
0 2
0 3
0 3
0 3
0 3
Output
1 2 3