눈싸움 1

Manfy의 사진 (cc-by-sa3.0)

$N$개의 정점을 가진 무방향 가중 그래프에서 $L$개의 나라가 IOI 동안 눈싸움을 벌인다. 처음에 각 나라는 어떤 정점 하나에 요새를 하나씩 가지고 있다.

시각 $0$에 각 나라는 눈싸움을 시작한다. 눈싸움은 다음과 같이 진행된다.

• 한 나라가 요새를 소유하고 있다면, 그 나라의 참가자들이 모두 같은 속도로 요새에서 뻗어 나가는 모든 간선을 따라 출발한다.

• 두 나라가 간선 위에서 만나면, 두 나라는 멈추어 서서 싸운다(영원히).

• 두 나라가 정점에서 만나면, 두 나라는 멈추어 서서 싸운다(영원히).

• 한 나라가 이미 다른 나라들이 싸우고 있는 정점에 도달하면, 그 싸움에 합류한다.

• 한 나라가 다른 어떤 나라보다 먼저 정점에 도달하면, 그 나라는 그 정점에 요새를 세운 뒤 규칙 1에 따라 그 정점에서 뻗어 나가는 간선을 따라 출발한다.

이 규칙들에 따라 특정 정점에는 최대 한 나라만 요새를 가질 수 있음에 유의한다. 두 나라가 한 정점에 동시에 도착하면, 그 정점에 도착한 참가자들은 그곳에 멈추어 무한히 오랫동안 싸우며 더 나아가지 않는다.

서로 싸우게 될 나라의 모든 쌍을 구한다.

점수

여러 테스트 케이스 그룹으로 풀이를 채점한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

1 | 8 | 그래프는 선형이다. 간선은 정확히 (0,1), (1,2), ..., (N-2, N-1)이다

2 | 9 | $L = 2$.

3 | 24 | 모든 간선에 대해 $w = 1$이다.

4 | 23 | 정점에서는 싸움이 일어나지 않는다.

5 | 29 | $1 \le N, M \le 2\,000$.

6 | 7 | 제한 없음.

첫 번째 줄에는 그래프의 정점 수, 나라 수, 간선 수를 각각 나타내는 세 정수 $N,L,M$ ($2 \le N \le 100\,000, 2 \le L \le 50, 1 \le M \le 100\,000$)가 주어진다. 이어서 각 나라의 시작 기지가 어느 정점에 있는지를 나타내는 정수가 담긴 $L$개의 줄이 주어진다. 마지막으로 각각 세 정수 $a, b, w$ ($0 \le a,b < N, a \neq b, 1 \le w \le 2\,000$)가 담긴 $M$개의 줄이 주어진다. 이는 영부터 번호를 매긴 정점 $a$와 $b$ 사이에 길이가 $w$인 (무방향) 간선이 있다는 뜻이다.

각 정점 쌍 사이에는 최대 하나의 간선만 있으며, 어떤 두 나라도 같은 정점에서 시작하지 않는다.

서로 싸우는 나라의 각 쌍 $a, b$에 대해 a b 한 줄을 출력한다. 여기서 $a < b$이며, 나라의 번호는 0부터 시작한다. 먼저 첫 번째 번호를 기준으로 정렬한 순서대로 출력한다. 예를 들어 $L = 3$이고 세 나라가 모두 서로 싸운다면 다음과 같이 출력한다.

0 1
0 2
1 2

이 예제에서 그래프는 사이클이며 거의 완전히 대칭이다. 나라 0과 나라 3 사이의 싸움은 간선 위에서 벌어지지만, 나머지 3번의 싸움은 정점에서 벌어진다.