레이팅 미적용그래프 알고리즘 강의를 막 수료한 소 베시는 자신만의 그래프 시각화 프로그램을 코딩하기 시작했다! 현재 그녀의 그래프 시각화 프로그램은 서로 다른 값의 정점을 가진 루트 있는 트리만 시각화할 수 있으며, 합치기(merging)라는 한 종류의 연산만 수행할 수 있다.
구체적으로, 합치기 연산은 트리에서 부모가 같은 서로 다른 두 정점을 하나의 정점으로 합치며, 합쳐진 정점의 값은 합쳐진 두 정점의 값 중 최댓값이고, 자식은 합쳐진 정점들의 모든 자식(있다면)의 합집합이다.
안타깝게도, 베시가 트리에 몇 번의 합치기 연산을 수행한 후 프로그램이 충돌하여 그녀가 수행한 합치기 연산의 기록을 잃어버렸다. 베시가 기억하는 것은 시작할 때의 트리와 모든 합치기 연산을 수행한 후의 최종 트리뿐이다.
초기 트리와 최종 트리가 주어질 때, 베시가 수행했을 수 있는 합치기 연산의 수열을 구하라. 그러한 수열이 존재함이 보장된다.
각 입력은 \(T\) (\(1\le T\le 100\))개의 독립적인 테스트 케이스로 이루어진다. 모든 테스트 케이스에 대한 \(N\)의 합이 \(1000\)을 넘지 않음이 보장된다.
출제자: Aryansh Shrivastava
배점
- 입력 2-6: 초기 트리와 최종 트리의 리프 개수가 같다.
- 입력 7-16: 추가 제약 조건이 없다.
출제자: Aryansh Shrivastava
첫째 줄에 독립적인 테스트 케이스의 개수 \(T\)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.
각 테스트 케이스의 첫째 줄에 베시의 초기 트리의 정점 개수 \(N\) (\(2 \leq N \leq 1000\))이 주어지며, 정점들은 \(1\dots N\)의 값을 가진다.
다음 \(N-1\)개의 줄에는 각각 공백으로 구분된 두 정점 값 \(v_i\)와 \(p_i\) (\(1 \leq v_i, p_i \leq N\))가 주어지며, 이는 베시의 초기 트리에서 값 \(v_i\)의 정점이 값 \(p_i\)의 정점의 자식임을 나타낸다.
다음 줄에 베시의 최종 트리의 정점 개수 \(M\) (\(2 \leq M \leq N\))이 주어진다.
다음 \(M-1\)개의 줄에는 각각 공백으로 구분된 두 정점 값 \(v_i\)와 \(p_i\) (\(1 \leq v_i, p_i \leq N\))가 주어지며, 이는 베시의 최종 트리에서 값 \(v_i\)의 정점이 값 \(p_i\)의 정점의 자식임을 나타낸다.
각 테스트 케이스에 대해, 합치기 연산의 개수를 출력한 다음, 그 길이의 순서 있는 합치기 연산 수열을 한 줄에 하나씩 출력한다.
각 합치기 연산은 공백으로 구분된 서로 다른 두 정수, 즉 합칠 두 정점의 값(순서는 무관)으로 출력해야 한다.
답이 여러 개이면 아무거나 출력한다.
1
8
7 5
2 1
4 2
5 1
3 2
8 5
6 2
4
8 5
5 1
6 54
2 5
4 8
3 8
7 8