U617292 NKOJ11745

小 E 有一棵有 n 个点的无根树，它的节点编号为 1 到 n ，其中第 i (i∈[1,n)) 条边连接节点 ui 和 vi (ui,vi∈[1,n]) 。同时他还有 m 条树上的路径，第 i (i∈[1,m]) 条路径为从节点 xi 到 yi 的路径 (xi,yi∈[1,n]) （请注意，可能存在 xi=yi 的情况，此时路径退化为一个点）。 但是小 T 并不喜欢这些路径，所以他想对这棵树进行一些破坏从而破坏路径。具体来说，小 T 可以做以下操作任意多次： 选择一个仍然存在的节点，并同时删除这个节点以及与之相连的边（即边的其中一个节点为删除的节点）。 小 T 认为，在经过一系列的破坏后，一条初始的连接节点 xi 和 yi 的路径被成功破坏当且仅当以下条件成立： 节点 xi 和 yi 中至少一个点已经被删除；或者节点 xi 和 yi 都存在，但此时已经不连通。 但是小 T 做破坏需要花费时间，而他还忙着去打乒乓球，所以他想知道他最少做多少次破坏操作才能使得 m 条路径都被破坏。同时，他不希望你只给个答案，所以小 T 要求你构造方案。

无

无