Fair Racing Game

R and his friends plan to have a racing game on Akina Mountain. The mountain is modeled as a directed graph with \(n\) nodes and \(m\) edges. They start at node 1 and try to reach node \(n\). The veteran driver mocania wants to assign a length between 1 and 9 (inclusive) to each edge so that every path from 1 to \(n\) has the same total length, ensuring fairness.

A valid assignment exists if and only if there is a potential function \(X(\cdot)\) defined on nodes such that for every edge \((u,v)\) that is part of some 1-to-\(n\) path, the assigned length equals \(X(v)-X(u)\) and \(1\le X(v)-X(u)\le 9\). In such a case, any path from 1 to \(n\) will have total length \(X(n)-X(1)\). Note that if the subgraph comprised of nodes which are both reachable from 1 and can reach \(n\) contains a cycle, no valid assignment exists, because a cycle would force a positive accumulated difference.

Your task is to output an assignment of edge lengths (in the input order) that meets these constraints. For edges that are not on any 1-to-\(n\) path (i.e. not in the critical subgraph), you may assign any number in \([1,9]\) arbitrarily (for example, 1). If there is no valid assignment (or if there is no path from 1 to \(n\)), output -1.

Note: The assignment for the edges that appear in any 1-to-\(n\) path is computed by first determining a potential \(X\) for each relevant node. We set \(X(1)=0\) and for every vertex \(v\) in the critical subgraph, we set \[ X(v)=\max_{u\to v} \{X(u)+1\}. \] Then, for each edge \((u,v)\) in the critical subgraph, the weight is \(X(v)-X(u)\). If any of these weights is greater than 9, the assignment is invalid, so output -1.

inputFormat

The first line contains two integers \(n\) and \(m\) \((2 \le n \le 10^5,\ 1 \le m \le 10^5)\), the number of nodes and edges.

Each of the following \(m\) lines contains two integers \(u\) and \(v\) \((1 \le u, v \le n)\) representing a directed edge from node \(u\) to node \(v\>.

outputFormat

If a valid assignment exists, print \(m\) integers in one line separated by spaces. The \(i\)th integer is the assigned weight for the \(i\)th edge in the input. Otherwise, print -1.

sample

4 4
1 2
2 4
1 3
3 4

1 1 1 1