QOJ.ac

QOJ

実行時間制限: 1.5 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓

#14720. 77G 네트워크

統計

야옹랜드(Meowland)의 지도는 $n$개의 정점과 $n - 1$개의 간선으로 이루어진 루트 있는 트리로 볼 수 있으며, 여기서 정점은 도시를 나타내고 간선은 두 도시를 연결하는 도로를 나타냅니다. 수도는 루트인 정점 $1$에 있습니다.

이제 야옹랜드는 일부 도시에 최신형 77G 네트워크 기지국을 설치하려고 합니다. 모든 도로가 충분한 네트워크 품질을 갖도록 보장하기 위해, 각 도로의 양 끝점 도시 중 적어도 한 곳에는 기지국이 있어야 합니다. 하지만 알 수 없는 기술적 문제로 인해 네트워크 시스템에는 $m$개의 결함이 있습니다. 결함 $i$는 다음과 같이 설명됩니다: 만약 도시 $x_i$에 기지국이 설치되면, $x_i$의 서브트리 내에 있으면서 $x_i$까지의 거리가 정확히 $y_i$인 모든 도시에는 기지국을 설치할 수 없습니다. 그렇지 않으면 기지국들이 서로 간섭을 일으켜 사용할 수 없게 됩니다.

위의 모든 요구 사항을 만족하도록 기지국을 설치할 도시들을 야옹랜드를 위해 선택해 주세요. 만약 올바른 방법이 존재하지 않는다면 No를 출력하세요.

입력

각 테스트 파일은 여러 개의 테스트 케이스를 포함합니다. 첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 10^3$)가 주어집니다. 이어서 테스트 케이스들에 대한 설명이 주어집니다.

각 테스트 케이스의 첫째 줄에는 도시의 수를 나타내는 정수 $n$ ($2 \le n \le 2 \times 10^5$)이 주어집니다.

둘째 줄에는 $n - 1$개의 정수 $f_2, f_3, \dots, f_n$ ($1 \le f_i < i$)이 주어지며, 여기서 $f_i$는 도시 $i$의 부모를 나타냅니다.

셋째 줄에는 결함의 수를 나타내는 정수 $m$ ($0 \le m \le 2 \times 10^5$)이 주어집니다.

다음 $m$개의 줄에는 각각 $i$번째 결함을 나타내는 두 정수 $x_i$와 $y_i$ ($1 \le x_i, y_i \le n$)가 주어집니다. 동일한 결함이 두 개 존재할 수도 있습니다.

각 테스트 파일에 대해, 모든 테스트 케이스에서 $n$의 합은 $2 \times 10^5$을 초과하지 않으며, 모든 테스트 케이스에서 $m$의 합도 $2 \times 10^5$을 초과하지 않음이 보장됩니다.

출력

각 테스트 케이스마다 올바른 방법이 없다면 한 줄에 No를 출력합니다.

그렇지 않다면 당신의 방법을 나타내는 세 줄을 출력합니다:

  • 첫째 줄에 Yes를 출력합니다.
  • 둘째 줄에 선택한 도시의 수를 나타내는 정수 $c$를 출력합니다.
  • 셋째 줄에 선택한 도시들을 나타내는 $c$개의 서로 다른 정수를 출력합니다.

올바른 방법이 여러 개 있다면 그중 아무것이나 출력해도 됩니다. 방법을 출력할 때 $c$개의 도시는 어떤 순서로 출력해도 됩니다.

예제

예제 입력 1

3
6
1 1 2 2 4
2
1 3
2 1
6
1 1 2 2 4
6
1 1
1 2
1 3
2 1
2 2
2 1
8
1 1 3 1 1 2 4
10
1 2
3 2
1 3
5 1
6 1
3 2
4 1
3 2
5 1
3 1

예제 출력 1

Yes
4
5 3 4 1
No
No

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.