QOJ.ac

QOJ

時間限制: 1.5 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓

#14720. 77G Network

统计

The map of Meowland can be regarded as a rooted tree with $n$ nodes and $n - 1$ edges, where nodes represent cities and an edge represents a road connecting two cities. The capital is at the root, node $1$.

Now Meowland wants to install brand-new 77G network base stations in some cities. To ensure that every road has sufficient network quality, at least one of the endpoint cities of each road must have a base station. However, due to unknown technical issues, the network system has $m$ faults. Fault $i$ can be described as follows: if a base station is installed at city $x_i$, then all cities within the subtree of $x_i$ whose distance to $x_i$ is exactly $y_i$ cannot install base stations; otherwise, the stations will interfere with each other and become unusable.

Please help Meowland choose some cities so that installing base stations in those cities satisfies all the above requirements. If no valid scheme exists, output No.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 10^3$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \le n \le 2 \times 10^5$), denoting the number of cities.

The second line contains $n - 1$ integers $f_2, f_3, \dots, f_n$ ($1 \le f_i < i$), where $f_i$ denotes the parent of city $i$.

The third line contains an integer $m$ ($0 \le m \le 2 \times 10^5$), denoting the number of faults.

Each of the next $m$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$), denoting the $i$-th fault. There may exist two identical faults.

For each test file, it is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$, and the sum of $m$ over all test cases does not exceed $2 \times 10^5$.

Output

For each test case, if there is no valid scheme, output a line No.

Otherwise, output three lines representing your scheme:

  • On the first line output Yes.
  • On the second line output an integer $c$, denoting the number of cities you choose.
  • On the third line output $c$ distinct integers, denoting the cities you choose.

If there are multiple valid schemes, you may output any one. When outputting the scheme, you may output the $c$ cities in any order.

Example

Sample Input 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

Sample Output 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.