Данил решил заработать денег, поэтому нашел подработку. Собеседование прошло хорошо, и его взяли на очень ответственную должность переключателя света.
Данил будет работать в корневом дереве (связном неориентированном графе без циклов) из n вершин, корнем которого является вершина 1. В каждой вершине находится комната, в которой может гореть свет. В обязанности Данила входит переключение света во всех комнатах поддерева вершины. Это значит, что если в какой-то комнате поддерева горит свет, он должен выключить его, иначе он должен включить его.
К сожалению (или к счастью), Данил очень ленивый. Он знает, что его начальник не собирается лично проверять выполнение работы. Вместо этого он будет присылать Данилу задания через личные сообщения на Workforces.
Задания бывают двух типов:
- pow v обозначает задание на переключение света в поддереве вершины v
- get v обозначает задание на подсчет количества комнат в поддереве v, в которых горит свет. Данил должен отправить начальнику ответ личным сообщением на Workforces.
Под поддеревом вершины v понимается все вершины, кратчайший путь от которых до корня дерева проходит через вершину v. В частности, сама вершина v лежит в поддереве вершины v.
Данил не собирается выполнять свою работу. Вместо этого он просит написать вас программу, которая будет отвечать начальнику за него.