QOJ.ac

QOJ

시간 제한: 1.5 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓

#14720. Red 77G

통계

El mapa de Meowland puede considerarse como un árbol con raíz con $n$ nodos y $n - 1$ aristas, donde los nodos representan ciudades y una arista representa una carretera que conecta dos ciudades. La capital está en la raíz, el nodo $1$.

Ahora Meowland quiere instalar nuevas estaciones base de la red 77G en algunas ciudades. Para garantizar que cada carretera tenga suficiente calidad de red, al menos una de las ciudades en los extremos de cada carretera debe tener una estación base. Sin embargo, debido a problemas técnicos desconocidos, el sistema de red tiene $m$ fallos. El fallo $i$ se puede describir de la siguiente manera: si se instala una estación base en la ciudad $x_i$, entonces todas las ciudades dentro del subárbol de $x_i$ cuya distancia a $x_i$ sea exactamente $y_i$ no pueden instalar estaciones base; de lo contrario, las estaciones interferirán entre sí y quedarán inutilizables.

Por favor, ayuda a Meowland a elegir algunas ciudades para que la instalación de estaciones base en esas ciudades satisfaga todos los requisitos anteriores. Si no existe ningún esquema válido, imprime No.

Entrada

Cada archivo de prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $T$ ($1 \le T \le 10^3$). A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene un entero $n$ ($2 \le n \le 2 \times 10^5$), que denota el número de ciudades.

La segunda línea contiene $n - 1$ enteros $f_2, f_3, \dots, f_n$ ($1 \le f_i < i$), donde $f_i$ denota el padre de la ciudad $i$.

La tercera línea contiene un entero $m$ ($0 \le m \le 2 \times 10^5$), que denota el número de fallos.

Cada una de las siguientes $m$ líneas contiene dos enteros $x_i$ y $y_i$ ($1 \le x_i, y_i \le n$), que denotan el $i$-ésimo fallo. Pueden existir dos fallos idénticos.

Para cada archivo de prueba, se garantiza que la suma de $n$ en todos los casos de prueba no supera $2 \times 10^5$, y la suma de $m$ en todos los casos de prueba no supera $2 \times 10^5$.

Salida

Para cada caso de prueba, si no existe ningún esquema válido, imprime una línea con No.

De lo contrario, imprime tres líneas que representen tu esquema:

  • En la primera línea imprime Yes.
  • En la segunda línea imprime un entero $c$, que denota el número de ciudades que eliges.
  • En la tercera línea imprime $c$ enteros distintos, que denotan las ciudades que eliges.

Si hay múltiples esquemas válidos, puedes imprimir cualquiera de ellos. Al imprimir el esquema, puedes imprimir las $c$ ciudades en cualquier orden.

Ejemplo

Entrada de ejemplo 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

Salida de ejemplo 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.