秋之国共有 $n$ 个人，分别编号为 $1,2,...,n$ ，一开始每个人都投了一票，范围 $[1,n]$ ，表示支持对应编号的人当总统。共有 $m$ 次预选，每次选取编号 $[l_i,r_i]$ 内的选民展开小规模预选，在该区间内获得超过区间大小一半的票的人获胜，如果没有人获胜，则由小 C 钦定一位候选者获得此次预选的胜利（获胜者可以不在该区间内），每次预选的结果需要公布出来，并且每次会有 $k_i$ 个人决定将票改投向该次预选的获胜者。全部预选结束后，公布最后成为总统的候选人，没有候选人的话输出 $-1$ 。

你决定设计你自己的软件包管理器。如果软件包 A 依赖软件包 B ，那么安装软件包 A 以前，必须先安装软件包 B 。同时，如果想要卸载软件包 B ，则必须卸载软件包 A 。现在你已经获得了所有的软件包之间的依赖关系。除 $0$ 号软件包以外，所有软件包都会依赖一个且仅一个软件包，而 $0$ 号软件包不依赖任何一个软件包。依赖关系不存在环。

现在有一些安装或卸载软件包的操作，需要求出这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包）。

给定一棵有 $n$ 个节点的无根树和 $m$ 个操作，操作有两类：

• 将节点 $a$ 到节点 $b$ 路径上所有点都染成颜色 $c$ ；
• 询问节点 $a$ 到节点 $b$ 路径上的颜色段数量（连续相同颜色被认为是同一段），

如“112221”由3段组成：“11”、“222”和“1”。

请你写一个程序依次完成这 $m$ 个操作。