One Walk

Time limit1sMemory limit1024 MB

Summary

Orient each edge of an undirected graph so that exactly one walk goes from S to E, or print -1 if that is impossible.

Level: Medium7 of 10
Topics: Graph, DFS
Solved: No attempts yet

Problem

Given an undirected simple graph $G$ . Assign a direction to every edge of $G$ so that there is exactly one walk from a vertex $S$ to another vertex $E$ . A walk is a path that may visit the same vertices and edges several times.

Input

The first line contains the number of vertices $N$ , the number of edges $M$ , the start vertex $S$ , and the end vertex $E$ , separated by spaces. ( $2 \leq N \leq 200\ 000$ ; $1 \leq M \leq 300\ 000$ ; $1 \leq S, E \leq N$ ; $S \neq E$ )

The next $M$ lines each contain two vertex numbers $u$ and $v$ connected by an edge, separated by a space. ( $1 \leq u, v \leq N$ )

Output

If no choice of edge directions makes the walk from $S$ to $E$ unique, print -1. Otherwise, print the direction of each edge in input order on one line. Print 0 if the edge is oriented as $u \rightarrow v$ , and 1 if it is oriented the other way. If several outputs satisfy the condition, print any of them.

Examples2

Example 1
Input
```
3 3 1 3
1 3
3 2
1 2
```
Expected output
```
0 1 1
```
Example 2
Input
```
4 3 1 4
1 3
3 2
1 2
```
Expected output
```
-1
```