언제 이어지는가
다이아몬드 V의견: 0
\(N\)개의 도시가 있다. 시간 순서대로 \(M\)개의 도로가 하나씩 건설되며, \(t\)번째로 건설되는 도로는 도시 \(a_t\)와 \(b_t\)를 양방향으로 잇는다.
\(Q\)개의 질문이 주어진다. 각 질문은 두 도시 \(u\), \(v\)로 이루어지며, \(u\)와 \(v\)가 처음으로 연결되는 시점을 묻는다. 즉, 앞에서부터 \(s\)개의 도로만 건설되었을 때 \(u\)에서 \(v\)로 갈 수 있게 되는 가장 작은 \(s\)를 구해야 한다. 끝까지 건설해도 연결되지 않으면 \(-1\)을, \(u = v\)이면 \(0\)을 출력한다.
각 질문마다 따로 계산하면 너무 느리다.
\(1 \le N \le 100{,}000\)
\(1 \le M \le 200{,}000\)
\(1 \le Q \le 200{,}000\)
\(1 \le a_t, b_t, u, v \le N\)
첫 줄에 \(N\), \(M\), \(Q\)가 주어진다.
다음 \(M\)개의 줄에 \(t\)번째 도로의 두 끝 도시 \(a_t\), \(b_t\)가 주어진다.
다음 \(Q\)개의 줄에 질문 \(u\), \(v\)가 주어진다.
각 질문에 대해 답을 한 줄에 하나씩 출력한다.
5 4 4
1 2
3 4
2 3
4 5
1 3
1 5
2 2
1 4
3
4
0
3도로 순서: (1,2),(3,4),(2,3),(4,5). 도시 1과 3은 세 번째 도로 (2,3) 건설 후 처음 연결되어 답 3. 1과 5는 네 번째 도로 (4,5) 건설 후 연결되어 답 4. (2,2)는 같은 도시라 0. 1과 4도 세 번째 도로 후 연결되어 3.
3 1 2
1 2
1 3
1 2
-1
1도로는 (1,2) 하나뿐. 도시 1과 3은 끝까지 연결되지 않아 \(-1\). 1과 2는 첫 도로로 연결되어 1.
골드 IIIriseoj 작성
출처 Original
평가 및 의견
언제 이어지는가
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
언제 이어지는가