시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 1427 | 439 | 277 | 26.206% |
N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 가장 처음에 모든 정점의 색은 검정색이다.
아래의 두 쿼리를 수행하는 프로그램을 작성하시오.
1 i
: i번 정점의 색을 바꾼다. (흰색 -> 검정색, 검정색 -> 흰색)2 v
: 모든 흰색 정점 u와 v까지의 거리 중에서 가장 가까운 거리를 출력한다. 이때, u와 v는 같아도 된다. v가 흰색이면 정답은 0이다. 트리에 흰색 정점이 없으면 -1을 출력한다.첫째 줄에 N (2 ≤ N ≤ 100,000)이 주어진다.
둘째 줄부터 N-1개의 줄에는 i번 간선이 연결하는 두 정점 번호 u와 v가 주어진다.
다음 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.
다음 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.
각각의 2번 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.
10 1 2 1 3 2 4 1 5 1 6 4 7 7 8 5 9 1 10 10 1 6 1 6 1 6 2 3 1 1 1 1 2 3 2 10 2 4 2 6
2 2 2 3 0