Optimal Edge Labeling for Minimizing Random Walk Score

Given an undirected connected graph with \(n\) vertices and \(m\) edges, where the vertices are numbered from \(1\) to \(n\) and the edges from \(1\) to \(m\), a random walk is performed starting from vertex \(1\). At each step, if the walker is at a vertex with degree \(d\), he chooses one of its adjacent edges uniformly at random and moves along that edge to the next vertex, earning a score equal to the label assigned to that edge. The walk stops when vertex \(n\) is reached, and the total score is the sum of the scores obtained along the way.

You are allowed to assign a distinct label from \(1\) to \(m\) to each edge. Your task is to choose an assignment of labels in order to minimize the expected total score earned by the random walker.

Hint: Since the random walk picks an edge uniformly, the expected contribution of each edge is proportional to the expected number of times it is traversed. Denote \(x_e\) as the expected number of times edge \(e\) is used. Then the expected total score is \(\sum_{e=1}^{m} x_e \cdot w(e)\). To minimize this sum when \(w(e)\) are a permutation of \(1, 2, \dots, m\), assign the smallest weights to the edges with the highest \(x_e\). It turns out that for this random walk on an undirected graph the values \(x_e\) are independent of the labeling and can be computed by solving a system of linear equations (equivalent to finding the electric potentials in a resistor network with \(V(1)=1\) and \(V(n)=0\); then the current on an edge is \(|V(u)-V(v)|\)).

Input Format: The first line contains two integers \(n\) and \(m\). Then \(m\) lines follow, each containing two integers \(u\) and \(v\) (\(1 \le u,v \le n\)) representing an edge between vertices \(u\) and \(v\).

Output Format: Output one line containing \(m\) integers. The \(i\)th integer denotes the label assigned to the \(i\)th edge (in the input order) in your assignment that minimizes the expected total score.

Note: If there are multiple optimal assignments, any one of them is accepted.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) representing the number of vertices and edges respectively. The following \(m\) lines each contain two integers \(u\) and \(v\), indicating an undirected edge between vertices \(u\) and \(v\).

outputFormat

Print a single line with \(m\) space‐separated integers. The \(i\)th integer is the label assigned to the \(i\)th edge in the input order. The labels must be a permutation of \(1\) to \(m\) that minimizes the expected total score of the random walk.

sample

2 1
1 2

1