Traffic Volume Survey

The Sublime Nation has $N$ cities numbered from $1$ to $N$. Modeled after Line 2 of the Seoul Metropolitan Subway, which passes Hanyang University, there are also $N$ roads numbered from $1$ to $N$. Each road connects two different cities, and no two roads connect the same pair of cities. In other words, the road network of the Sublime Nation is a simple graph. Every city can reach every other city by road.

Jeonghwi joined Hyundai Mobis and was assigned to analyze traffic volume on each road to help develop efficient self-driving software. Given the departure and destination cities of $M$ vehicle groups, you must find the number of vehicles that pass through each road.

The $i$-th vehicle group has $w_i$ vehicles. It travels from its departure city to its destination city, using each city and each road at most once. There may be several such routes. Since the worst case must be considered, each road that the group might use counts all $w_i$ vehicles as passing through it. In other words, you must count the vehicles that could pass through each road.

Jeonghwi solved this in $O(NM)$ time, but he wants a faster method. Help him solve the problem efficiently.

Print $N$ lines. On the $i$-th line, print the number of vehicles that could pass through the $i$-th road.