문제
정올이는 크리스마스를 기념해 N개의 정점으로 이루어진 크리스마스 트리를 청소하려 한다.
정올이는 두개의 리프 정점을 지정해, 두 리프 정점을 지나는 경로를 따라 수건으로 먼지를 털어내는 것을 반복할 것이다. 이 과정에서 걸리는 시간은 경로 상의 간선의 개수와 같다. 하지만 리프 정점은 연약하기에, 리프 정점은 정확히 1번씩만 지정할 것이다.
모든 간선을 최소 한번씩 수건으로 청소하기 위한 최소 시간을 구해보자.
단순히 이를 해결하는 것은 너무 지루했던 정올이는, 크리스마스 트리의 모양을 조금 바꾼 형태에서 위 물음을 해결하고자 한다. 구체적으로, V번 정점에 1개의 간선을 추가해 1개의 새로운 리프를 생성할 것이다. 이 과정에서 기존에 리프였던 정점이 리프가 아니게 될 수도 있음에 주의하자.
각각의 변화된 트리에서 정올이의 물음을 해결하자. 변화는 누적되지 않는다는 것에 주의하자.
입력
첫 줄에 초기 트리의 정점의 개수 N(1<=N<=100000)과 쿼리의 개수 Q(1<=Q<=100000)이 주어진다.
그 다음 N-1줄에 걸쳐 초기 트리의 간선에 대한 정보가 주어진다.
그 다음 Q줄에 걸쳐 트리의 변화가 주어진다. 각 줄은 수 S와, 그 뒤를 이어 길이 S의 배열 A_1, ..., A_S가 주어진다. 이는 각 A_i번 정점에 간선을 추가한 형태의 트리에서의 답을 구하라는 의미이다. 이때 배열에 중복된 수가 존재할 수 있다.
출력
Q개의 질의에 대한 답을 줄바꿈으로 구분하여 출력하시오. 만약 모든 간선을 청소할 방법이 없다면 -1을 대신 출력하여라.
예제
7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1
-1
10
8
로그인해야 코드를 작성할 수 있어요.