시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 564 | 242 | 174 | 45.910% |
남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 있는 도로들을 새로 만드는 계획이다. 도로 정비 계획은 두 도시에 대한 정보가 주어지는데, 도로를 정비하는 일은 매우 큰 일이기에 계획을 순서대로 하나씩 시행해 나갈 것이다.
Zych는 차후 도로 정비 계획에 참고하기 위하여, 각 도시들이 수도에 방문하는데 최소 몇 개의 도시들을 방문해야 하는지 조사하기로 하였다.
남규나라의 초기 도시상태가 주어지고 도로 정비계획이 주어질 때, 한 도로가 정비될 때마다 각 도시별로 수도를 방문하는 데 최소 방문 도시들을 출력하시오.
첫째 줄에는 도시의 개수 n,도로의 개수 m이 주어진다. 다음 m개의 줄에는 두 도시가 주어진다.(2≤n≤1,000,1≤m≤100,000)
다음 줄에는 도로 정비 계획에 들어가 있는 도로의 수 q가 주어지고, 다음 q줄에는 i j가 주어지는데 두 도시 i,j를 잇는 도로를 만든다.. (1≤q≤500, 1≤i,j≤n)
수도는 1번도시이다.
q줄에 각 도시별로 수도를 방문하는 데 최소 방문 도시들을 출력하시오. 만약 수도를 방문하지 못한다면 -1을 출력하시오.
5 3 1 2 1 3 2 4 5 2 3 4 5 3 4 1 4 1 5
0 1 1 2 -1 0 1 1 2 3 0 1 1 2 3 0 1 1 1 2 0 1 1 1 1