import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string; auto rdsp(){return readln.splitter;} void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;} void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);} void main() { int n; readV(n); auto g = Graph!int(n); foreach (i; 0..n-1) { int u, v; readV(u, v); --u; --v; g.addEdgeB(u, v); } auto t = g.makeTree.rootify(0); auto st1 = SList!int(0), st2 = SList!int(); while (!st1.empty) { auto u = st1.front; st1.removeFront(); st2.insertFront(u); foreach (v; t.children(u)) st1.insertFront(v); } auto a = new int[](n), b = new int[](n); while (!st2.empty) { auto u = st2.front; st2.removeFront(); a[u] = 1; foreach (v; t.children(u)) { a[u] += max(a[v]-1, b[v]); b[u] += max(a[v], b[v]); } } writeln(max(a[0], b[0])); } struct Graph(N = int) { alias Node = N; Node n; Node[][] g; alias g this; this(Node n) { this.n = n; g = new Node[][](n); } void addEdge(Node u, Node v) { g[u] ~= v; } void addEdgeB(Node u, Node v) { g[u] ~= v; g[v] ~= u; } } struct Tree(Graph) { import std.algorithm, std.container; alias Node = Graph.Node; Graph g; alias g this; Node root; Node[] parent; int[] size, depth; this(ref Graph g) { this.g = g; this.n = g.n; } ref auto rootify(Node r) { this.root = r; parent = new Node[](g.n); depth = new int[](g.n); depth[] = -1; struct UP { Node u, p; } auto st1 = SList!UP(UP(r, r)); auto st2 = SList!UP(); while (!st1.empty) { auto up = st1.front, u = up.u, p = up.p; st1.removeFront(); parent[u] = p; depth[u] = depth[p] + 1; foreach (v; g[u]) if (v != p) { st1.insertFront(UP(v, u)); st2.insertFront(UP(v, u)); } } size = new int[](g.n); size[] = 1; while (!st2.empty) { auto up = st2.front, u = up.u, p = up.p; st2.removeFront(); size[p] += size[u]; } return this; } auto children(Node u) { return g[u].filter!(v => v != parent[u]); } } ref auto makeTree(Graph)(ref Graph g) { return Tree!Graph(g); }