Tollgate

A country has a road network of $N$ cities and $M$ roads. Each road directly connects two different cities, and no two roads cross in the middle of a road. Roads carry traffic in both directions, and there is at most one road between a pair of cities. All roads have the same length. Along the road network you can travel from any city to every other city. The population of every city is a natural number of at least 1, and every city has zero or more restaurants (a restaurant here means a famous eating place).

A cycle is a set of roads that lets you start at one city, follow some roads, and come back to the original city. No road may be used twice in a cycle. This country's road network has an unusual property: every road belongs to at most one cycle. For example, a network built from three different paths joining the same two cities is never given in this problem, because each of its roads belongs to two cycles.

During one year, every person in this country visits every restaurant exactly once. A person living in city $A$ visiting a restaurant in city $B$ means leaving $A$, visiting exactly one restaurant in $B$, and coming back to $A$. No other restaurant is visited on the way. The person walks a shortest route from $A$ to $B$ and returns along the same route. When several shortest routes exist, the person picks one of them with equal probability.

The country is short on money, so it will install a tollgate on exactly one road. The toll must be paid in whichever direction the tollgate is passed, and the toll is the same regardless of the distance traveled.

Read the number of cities, the population and restaurant count of every city, and the road network, then write a program that finds the road with the largest expected toll income over one year. If several roads have the same expected income, print all of them.

The first line has the integer $N$, the number of cities, and the integer $M$, the number of roads, separated by a space, with $2 \le N \le 200{,}000$ and $2 \le M \le 300{,}000$. Cities are numbered 1 through $N$.

Each of the next $N$ lines has the population and the restaurant count of one city as two non-negative integers separated by a space. The first number is the population and the second number is the restaurant count. The lines come in city number order.

Each of the following $M$ lines has one road as a pair of city numbers separated by a space. In every pair the first number is smaller than the second. The pairs come in increasing order of the first number, and pairs sharing a first number come in increasing order of the second number.

Intermediate values can exceed the range of a 32-bit unsigned variable, so you may need a 64-bit variable.

On the first line print $K$, the number of roads whose expected toll income is largest when a tollgate is installed on it. On each of the next $K$ lines print one such road as a pair of city numbers separated by a space. Print the pairs in the same order as the input.