A term is a tree-like structure used in mathematics, computer science, and philosophy to identify entities in a domain of discourse. What is remarkable about terms is that they offer a direct encoding of such entities that a computer can process. For a particular domain of discourse, the set of terms is parametric on a set of variables V and a set of function symbols F; it is inductively defined by the following rules: • Any variable is a term. • Any function symbol f with ar(f) = 0 is a term. • Any expression f(t1,...,tn), with ar(f) = n ≥ 1 and each argument ti a term (1 ≤ i ≤ n), is a term. Here ar is a function from the set of function symbols F to the natural numbers. For each f ∈ F, the expression ar(f) denotes the number of arguments of f. For example, for F = {a,f,g,h} with ar(a) = 0, ar(g) = ar(h) = 2, ar(f) = 3, and X a variable, let t be the term f(g(h(a,a),h(a,a)),h(a,X),g(h(a,a),h(a,a))). The term t can be graphically represented as a labeled tree with 18 vertices as inn the picture on the right. A string representation of a term, in general, can be unneces- sarily lengthy and thus inefficient to compute with. An important observation to cope with this limitation is that subterms can be shared and then a tree can be represented by a directed acyclic multigraph (or dam). In a dam, vertices are labeled with function symbols from F and variables from V, and edges are labeled with the argument position of the corre- sponding subterm in the term structure. Note that there can be more than one edge between any pair of vertices of a dam. The following dams are representations of the term t abovementioned. In these representations, for example, the topmost function symbol f is applied over three terms of which the first and third are shared: this is indicated by labels 1 and 3 in the edges with source f. Although these dams represent the same term, they differ in the number of vertices: the one on the left has 7 vertices and the one on the right has 6 vertices. There can be many other dams representing the term t, but any of them requires at least 6 vertices.
2/2 In this problem, the interest is in computing the size (with respect to the number of vertices) of a dam representing a term which shares the most number of subterms. More precisely, the goal is to compute the minimum number of vertices required to represent a term as a dam. Input The input consists of several test cases, each being a line containing a string representation of a term s(1≤|s|≤105). AvariableinVisrepresentedinsbyastringv(1≤|v|≤20)madeoflowercase and uppercase letters of the English alphabet starting with an uppercase letter. Similarly, a function symbol in F is represented in s by a string f (1 ≤ |f| ≤ 20) made of lowercase and uppercase letters of the English alphabet starting with a lowercase letter. You can assume that s contains at most 2 000 variables and function symbols (not necessarily different). Output For each test case output the minimum number of vertices required to represent s as a dam. Sample Input f(g(h(a,a),h(a,a)),h(a,X),g(h(a,a),h(a,a))) h(a,b) h(a,a) h(A,a) CCPL f(a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a) f(g(a,X,a),g(a,a,X)) f(g(a,X,a),g(a,X,a)) Sample Output 6 3 2 3 1 2 5 4