시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 101 78 56 78.873%

문제

하나의 은하 안에는 여러 행성들이 존재한다. 문명의 기술 발전으로 은하 내의 모든 행성들은 서로 여행할 수 있게 되었다.

드디어 오늘, 80,000 광년 떨어진 다른 은하와 우리 은하를 연결하는 은하 철도가 개통된다.

은하 철도가 개통되면 더 많은 행성을 여행할 수 있다는 사실에 은하 내 모든 행성의 주민들은 들떠있는 분위기이다.

우주철도공사 G-Express는 앞으로의 은하 철도 계획을 발표하였다.

우주는 너무 넓기 때문에, G-Express사는 은하가 연결될 때마다 몇 개의 행성들이 서로 여행할 수 있게 되었는 지를 알려주고자 한다.

G-Express사 기술개발팀의 직원인 당신에게 이 프로그램의 업무 요청이 들어왔다. 각 은하들의 행성 수와 철도 계획이 주어지면 해당 철도를 이용할 수 있는 행성들의 수를 실시간으로 안내하는 프로그램을 만들자.

입력

첫 번째 줄에 은하의 수 N과 철도의 개수 M이 주어진다.

두 번째 줄부터 N개의 줄에 N개의 각 은하 내에 존재하는 행성들의 수가 1번 은하부터 차례대로 주어진다. (행성을 세는 단위는 조(1012) 단위이다.)

그리고 N+2 번째 줄부터 M개의 줄에 걸쳐 은하와 은하 사이를 잇는 철도가 주어진다. 같은 은하 사이에 여러 개의 철도가 건설될 수 있다.

입력되는 N은 2 ≤ N ≤ 100,000, M은 1 ≤ M ≤ 100,000이고, 각 은하의 행성 수는 100(조)개를 넘지 않으며 아무 행성도 없는 경우는 없다.

출력

철도가 연결될 때마다 해당 철도를 이용할 수 있는 행성들의 수를 한 줄씩 출력한다.

예제 입력 1

5 4
3
9
10
11
15
1 2
2 3
4 5
4 3

예제 출력 1

12
22
26
48

예제 입력 2

5 4
3
1
4
15
9
1 2
3 1
2 3
2 4

예제 출력 2

4
8
8
23

노트

입력 데이터가 큰 관계로, 빠른 입출력을 사용하는 것을 권장합니다.

출처

University > 전북대학교 > 2019 전북대학교 프로그래밍 경진대회 G번

  • 어색한 표현을 찾은 사람: jaehoo1
  • 문제를 만든 사람: joonas