시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB0000.000%

문제

어느 나라에는 N 개의 도시와 M개의 도로로 구성된 도로망이 있다. 각 도로는 서로 다른 두 도시를 직접 잇는 형태이며, 서로 다른 두 도로가 도로의 중간에서 교차하는 일은 없다. 도로는 양방향 통행이 가능하고, 한 쌍의 도시 사이에는 최대 하나의 도로가 있다. 모든 개별 도로들의 길이는 동일하다. 또한, 도로망을 통해서 어떤 도시에서든 다른 모든 도시로 이동이 가능하다. 모든 도시의 인구수는 1 이상의 자연수이다. 각 도시에는 0개 이상의 맛집이 있다. (맛집은 유명한 음식점을 말한다.)

이 나라의 도로망을 조사해 보니 특이한 점을 한 가지 발견하게 되었다. 한 도시에서 출발해서 몇 개의 도로들을 따라가면 다시 원래의 도시로 돌아올 수 있는 도로들의 집합을 사이클이라고 부른다. (단, 같은 도로를 두 번 이상 사용할 수 없다.) 이 나라의 도로망의 특이한 점은 모든 개별 도로는 최대 하나의 사이클에 속한다는 것이다. 예를 들어, 아래 그림에서 원이 도시들이고 선이 도로라고 하면 각 도로들이 모두 2개의 사이클에 속하게 되므로 이 문제에서는 주어지지 않는 경우이다.

이 나라의 모든 사람들은 일 년 동안 모든 맛집을 한 번씩만 다녀온다. A 도시에 사는 사람이 B 도시의 맛집을 다녀온다는 것은 A에서 출발하여 B에 있는 하나의 맛집만 방문하고 A로 다시 돌아오는 것을 말한다. (즉, 그 과정에서 다른 맛집을 방문하지 않는다.) 또, A에서 B의 맛집을 다녀오는 경우 A에서 B로 가는 가장 짧은 길을 왕복한다. 가장 짧은 길이 여러 개 존재하는 경우는 동일한 확률로 그 중 하나를 선택한다. 

이 나라의 재정이 최근 부족하여 도로들 중 단 하나에 톨게이트를 설치하려고 한다. 톨게이트를 어느 방향으로 통과하든 비용을 지불해야 하며 이동 거리에 관계없이 모두 동일한 비용을 지불한다. 

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

아래 그림의 예를 보자. 그림에서 원 안에 있는 수는 도시의 번호이며, 원 옆에 있는 두 수는 각각 도시의 인구수와 맛집의 수이다. 화살표는 1번 도시와 5번 도시 간의 가장 짧은 길의 한 예이다. 1번 도시에서 2번 도시로 가는 가장 짧은 길은 한 가지 뿐이지만, 1번 도시에서 5번 도시로 가는 가장 짧은 길은 두 가지이다. 모든 상황을 고려하면 4번 도시와 5번 도시 사이에 톨게이트를 설치하는 것이 가장 많은 통행료 수입을 기대할 수 있음을 알 수 있다. 

입력

첫 줄에는 도시의 수를 나타내는 정수 N 과 도로의 수를 나타내는 정수 M이 공백을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 200,000, 2 ≤ M ≤ 300,000이다. 도시는 1번부터 N 번 까지 번호가 붙어 있다. 둘째 줄부터 N 개의 줄에는 각 도시의 인구수와 맛집의 수가 두 개의 음 아닌 정수로 공백을 사이에 두고 주어진다. 첫 번째 수가 인구수이며 두 번째 수가 맛집의 수이다. 인구수와 맛집의 수는 도시의 번호 순서대로 주어진다. 이후 M개의 줄에는 도로의 정보가 도시 번호의 쌍으로 공백을 사이에 두고 주어진다. 도시 번호의 쌍은 항상 앞 번호가 뒤 번호보다 작은 형태이다. 도시번호의 쌍들은 앞 번호가 작은 것부터 주어지며, 같은 앞 번호들 간에는 뒤 번호가 작은 것부터 주어진다. 계산 과정에서 32비트 자연수 변수가 표현할 수 있는 범위를 넘어서 64비트 자연수 변수를 사용해야 할 수도 있음에 주의하라.

출력

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

예제 입력 1

5 4
1 1
1 1
1 1
1 1
1 1
1 2
2 3
3 4
4 5

예제 출력 1

2
2 3
3 4

예제 입력 2

5 5
1 1
1 1
2 1
2 1
5 1
1 2
1 3
2 4
3 4
4 5

예제 출력 2

1
4 5