시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 101 | 46 | 28 | 40.580% |
Your son, JOI-kun, likes to have pets. There are N huts for a pet, numbered 1 through N, in your house garden. There are N − 1 paths connecting huts bidirectionary, and it is known that for any two huts, it is possible to move between them following some paths. Each hut can have at most one pet.
JOI-kun wants to have cats and dogs, but he is worried that they would often fight each other. Then for a situation where each hut has one of the following states: having a cat, having a dog, and having no pet, he defines the danger level of the garden as follows:
After defining the danger level, JOI-kun starts making a plan to use the garden for Q days. Initially, no hut has an pet. The plan on the i-th day is one of the following:
You, as a parent, are responsible to check if your son’s plan is dangerous or not. Specifically, you need to find the danger level of the garden after the plan on each day during the Q days.
Here, the plan on the (j + 1)-th day is cat if Tj = 1, dog if Tj = 2, and neighbor if Tj = 3, with vj.
3 1 2 2 3 4 1 1 1 3 2 2 3 2
0 0 2 0
5 1 2 2 3 2 4 4 5 5 1 3 2 5 1 2 2 1 3 2
0 1 1 2 1
Consider the case where there are 5 huts and 4 paths, connecting between hut 1 and hut 2, between hut 2 and hut 3, between hut 2 and hut 4, and between hut 4 and hut 5.