题目描述

Alice和Bob在玩游戏。 有一棵$N$个节点的树，Alice和Bob轮流操作，Alice先手，一开始树上所有节点都没有颜色，Alice每次会选一个没有被染色的节点并把这个节点染成红色（不能不选），Bob每次会选一个没有被染色的节点并把这个节点染成蓝色（不能不选）。当有人操作不了时，游戏就终止了。 Alice的最终得分为红色连通块个数，Bob的最终得分为蓝色连通块个数。设Alice的得分为$K_A$，Bob的得分为$K_B$，Alice想让$K_A-K_B$尽可能大，Bob则想让$K_A-K_B$尽可能小，假如两人都采取最优策略操作，那么$K_A-K_B$是多少。

输入

第一行包含一个整数$N$，接下来$N$行，每行包含两个整数$u_i,v_i$，代表树中有一条连接$u,v$的边。

输出

第一行包含一个整数，表示答案。

输入样例

4
1 2
1 3
1 4

输出样例

1

提示

【样例输入2】

5
1 2
1 3
1 4
1 5

【样例输出2】

-1

【数据规模与约定】 对于40%的数据，$N≤20$。 另有10%的数据，保证给定的树是一条链。 对于100%的数据，$N≤100000$。

边行数说明

输入是一棵N个节点的树，因此读取N-1行边。原输入小节误写N行，两组公开样例均为N-1行。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。