Problem I
Cactus Shoppe
After retirement, UT CS professors go to a farm in upstate Texas where they garden and do research to their hearts’ content. Oftentimes these two interests overlap, as is the case with the amazing Upstate Texas Cactus Shoppe (UTCS).
For those of us who are not retired CS professors, a cactus is an undirected graph where each edge belongs to at most one simple cycle. Here are some pictures of cactuses:
![\includegraphics[width=0.35\textwidth ]{cactus1small}](/problems/utipc19.cactusshoppe/file/statement/en/img-0001.jpg)
![\includegraphics[width=0.35\textwidth ]{cactus2small}](/problems/utipc19.cactusshoppe/file/statement/en/img-0002.jpg)
Here is a picture of a cactus graph:
![\includegraphics[width=0.80\textwidth ]{cactus_graph}](/problems/utipc19.cactusshoppe/file/statement/en/img-0003.png)
The UTCS has a single cactus. Each vertex in the cactus has
a flower identifier
To conduct a purchase at the UTCS, a professor comes in with
a flower identifier
All this cutting and pruning is hard work, especially for the retired. Can you help answer their queries?
Input
The first line has three space-separated integers
The next
Output
For each query made by a professor, output the number of
connected components that remain when removing all the vertices
that are not divisible by
Sample Input 1 | Sample Output 1 |
---|---|
3 2 5 15 10 6 1 2 2 3 5 14 10 3 2 |
1 0 1 2 1 |
Sample Input 2 | Sample Output 2 |
---|---|
5 6 4 6 15 9 20 12 1 2 2 3 3 1 2 4 4 5 5 2 5 3 7 2 |
1 1 0 2 |