| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 2048 MB | 10 | 5 | 5 | 50.000% |
Old Orhei (Orheiul Vechi) is a natural and historical complex located on a narrow bend of the Răut River. It consists of $N$ archaeological vestiges and $M$ one-way roads between some pairs of vestiges. Every road has a unique index between 1ドル$ and $M,ドル defined by the input order in which it is given. Please refer to the Examples section for visualizing such a configuration.
Recently an array left by the Cucuteni–Trypillia civilization was discovered by the local scientists. The array consists of $T$ integers with values between 1ドル$ and $M$. In order to figure out the mystical meaning of this array, the new intern will be instructed to follow this procedure:
At the beginning, the intern starts at some initial archaeological vestige. The other scientists start broadcasting to him a contiguous sub-array of the main array (first broadcasting the first element of the subarray, then the second one, and so on). The intern then changes his location depending on the following rules:
With the occasion of the 8ドル$-th European Junior Olympiad in Informatics, the local scientists have asked you to help them perform the following $Q$ queries:
Your task is to answer correctly to all the queries of type 1ドル$.
The first line contains two space-separated integers $N$ and $M,ドル the number of archaeological vestiges and one-way roads.
The next $M$ lines contain the description of the roads. In particular, line i will contain two space-separated numbers indicating that the $i$-th road starts in $X_i$ and ends in $Y_i$. There can exist roads for which $X_i = Y_i$ as well as pairs of roads for which $X_i = X_j$ , $Y_i = Y_j$ but $i \ne j$.
The next line contains an integer $T,ドル the length of the found array.
The next line contains $T$ space-separated integers $A_1 ,A_2, \dots ,A_T,ドル representing the array elements.
The next line contains an integer $Q,ドル the number of queries.
The next $Q$ lines contain the query description:
For each query of type 1ドル$ output the answer on a separate line.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $Q = 1$ (The only existing query is of type 1ドル$). |
| 2 | 16 | $N = 2$ |
| 3 | 17 | $M = N - 1,ドル $X_i = i,ドル $Y_i = i + 1$. |
| 4 | 31 | There are no queries of type 2ドル$. Additionally, $T ≤ 3 \cdot 10^4$. |
| 5 | 29 | No additional constraints. |
5 6 1 2 3 2 4 2 2 5 5 1 4 5 6 2 1 4 2 5 3 3 1 3 5 2 1 3 5 2 1 1 2 3
1 1 2
Initially, the intern starts in vestige 2, and the sub-array broadcasted is [4, 2, 5].
The number 4ドル$ is broadcasted so the intern moves to vestige 5ドル,ドル since the road with index 4ドル$ can be traversed.
Afterwards, number 2ドル$ is broadcasted. The intern remains in the same location as the road with index 2ドル$ cannot be used.
Finally, number 5ドル$ is broadcasted, and the intern can traverse the corresponding road, so the intern ends up in vestige 1ドル,ドル which is the answer for that corresponding query.
3 3 1 2 2 3 3 1 4 3 1 1 2 4 1 1 2 3 2 2 2 1 1 2 3 1 1 4 2
2 1 3
2 3 1 1 1 2 1 2 4 1 1 2 3 3 1 1 2 1 2 1 2 1 1 2 1
1 2
For the first query the intern will traverse the first road going from vestige 1ドル$ to itself two times in a row, hence the answer for this query is 1ドル$.
The second query updates the first element of the array to 2ドル$.
During the third query the number 2ドル$ is first broadcasted to the intern located in vestige 1ドル$. Since the corresponding road is adjacent to this vestige, the intern traverses it and changes his location to vestige 2ドル$. Finally, number 1ドル$ is broadcasted, and the intern cannot traverse the corresponding road, so the intern's end location is vestige 2ドル$.