톨게이트

어느 나라에 $N$개의 도시와 $M$개의 도로로 이루어진 도로망이 있다. 각 도로는 서로 다른 두 도시를 직접 잇고, 서로 다른 두 도로가 도로 중간에서 교차하는 일은 없다. 도로는 양방향으로 통행할 수 있고, 한 쌍의 도시 사이에는 도로가 많아야 하나 있다. 도로의 길이는 모두 같다. 또, 도로망을 따라가면 어떤 도시에서든 다른 모든 도시로 갈 수 있다. 모든 도시의 인구수는 1 이상의 자연수이고, 각 도시에는 맛집(유명한 음식점)이 0개 이상 있다.

한 도시에서 출발해 도로 몇 개를 따라가면 다시 원래 도시로 돌아올 수 있는 도로들의 집합을 사이클이라고 한다. 단, 같은 도로를 두 번 이상 쓸 수 없다. 이 나라 도로망의 특이한 점은 모든 도로가 많아야 하나의 사이클에만 속한다는 것이다. 예를 들어 같은 두 도시를 잇는 서로 다른 세 개의 경로로 이루어진 도로망은 각 도로가 두 개의 사이클에 속하므로 이 문제에서는 주어지지 않는다.

이 나라 사람은 모두 일 년 동안 모든 맛집을 한 번씩만 다녀온다. $A$ 도시에 사는 사람이 $B$ 도시의 맛집을 다녀온다는 것은 $A$에서 출발해 $B$에 있는 맛집 하나만 방문하고 $A$로 돌아오는 것을 말한다. 즉, 그 과정에서 다른 맛집은 방문하지 않는다. 또, $A$에서 $B$의 맛집을 다녀올 때는 $A$에서 $B$로 가는 가장 짧은 길을 왕복한다. 가장 짧은 길이 여러 개 있으면 그중 하나를 같은 확률로 고른다.

이 나라는 최근 재정이 부족해져서 도로 중 단 하나에만 톨게이트를 설치하려고 한다. 톨게이트는 어느 방향으로 통과하든 비용을 내야 하며, 이동 거리와 상관없이 비용은 모두 같다.

도시의 수, 도시별 인구수와 맛집의 수, 그리고 도로망을 입력받아 일 년 동안 가장 많은 통행료 수입을 기대할 수 있는 도로를 찾는 프로그램을 작성하라. 기댓값이 같은 도로가 여러 개면 모두 출력해야 한다.

첫 줄에는 도시의 수를 나타내는 정수 $N$과 도로의 수를 나타내는 정수 $M$이 공백을 사이에 두고 주어진다. 단, $2 \le N \le 200{,}000$, $2 \le M \le 300{,}000$이다. 도시는 1번부터 $N$번까지 번호가 붙어 있다.

둘째 줄부터 $N$개의 줄에는 각 도시의 인구수와 맛집의 수가 음이 아닌 정수 두 개로 공백을 사이에 두고 주어진다. 첫 번째 수가 인구수이고 두 번째 수가 맛집의 수이며, 도시의 번호 순서대로 주어진다.

이후 $M$개의 줄에는 도로의 정보가 도시 번호의 쌍으로 공백을 사이에 두고 주어진다. 도시 번호의 쌍은 항상 앞 번호가 뒤 번호보다 작다. 쌍은 앞 번호가 작은 것부터 주어지고, 앞 번호가 같으면 뒤 번호가 작은 것부터 주어진다.

계산 과정에서 32비트 자연수 변수가 표현할 수 있는 범위를 넘어 64비트 자연수 변수를 써야 할 수도 있으니 주의하라.

첫 줄에 톨게이트를 설치하면 통행료의 기댓값이 가장 높은 도로들의 수 $K$를 출력한다. 이후 $K$개의 줄에 그 도로들을 도시 번호의 쌍으로 공백을 사이에 두고 출력한다. 도시 번호의 쌍을 출력하는 순서는 입력과 같아야 한다.