Distinguish Tree Generation Methods

Y recently obtained a random number generator and used it to generate trees with n nodes (with n = 1000). Recall that a tree is an undirected connected graph with no cycles.

She used four different methods to generate a tree:

1. First generate a permutation \(p_1,p_2,\dots,p_n\) of \(\{1,2,\dots,n\}\). Then, for every \(i\) from \(2\) to \(n\), add an edge between \(p_i\) and \(p_j\), where \(j\) is chosen uniformly at random from \(\{1, 2, \dots, i-1\}\).

2. First generate a permutation \(p_1,p_2,\dots,p_n\) of \(\{1,2,\dots,n\}\). Then, for every \(i\) (\(2 \le i \le n\)), add an edge between \(p_i\) and \(p_j\), where \(j\) is chosen uniformly at random from \(\{\lfloor i/2\rfloor, \lfloor i/2\rfloor+1, \dots, i-1\}\).

3. Start with a graph of n isolated nodes. Repeatedly pick an unordered pair \(u,v\) uniformly at random. If \(u\) and \(v\) are not already connected, add the edge \((u,v)\). Continue until the graph is connected.

4. Among all different labeled trees on \(n\) nodes (two trees are considered different if there is an edge that appears in one tree but not in the other), choose one tree uniformly at random.

Y generated many trees with n = 1000 nodes by one of these four methods, but she forgot which tree was generated by which method. Your task is to decide, given a tree with 1000 nodes, which method was most likely used to generate it. It is guaranteed that the input tree was produced by one of the above methods.

Note: Since the trees generated by methods 3 and 4 are uniformly random spanning trees, they are statistically indistinguishable by simple invariant measurements. Thus, you may assume that certain structural properties (such as maximum degree and diameter) can be used to heuristically distinguish between the methods.

Heuristic suggestion:

• Method 1 (random recursive tree) tends to have a relatively high maximum degree. (Typically, \(\max degree \gtrsim 7\) for \(n=1000\)).
• Method 2 (restricted parent selection) produces trees close to nearly binary trees (so the maximum degree is at most 3).
• Methods 3 and 4 (uniform choices) yield trees with an intermediate maximum degree. Moreover, uniform trees tend to have a larger diameter (often \(>15\)).

You may use the following heuristic in your solution:

Compute d_max = maximum degree in the tree
Compute diam = diameter of the tree (the length of the longest simple path)

if (d_max ≤ 3):
    answer = 2
else if (d_max ≥ 7):
    answer = 1
else:  // i.e. when 4 ≤ d_max ≤ 6
    if (diam > 15):
        answer = 4
    else:
        answer = 3

Output the method number you determine (an integer between 1 and 4).

inputFormat

The input consists of:

1. An integer n (which will be 1000 in the actual test cases) representing the number of nodes.
2. n-1 lines follow, each containing two integers u and v representing an undirected edge between nodes u and v.

You may assume the given graph is a tree.

outputFormat

Output a single integer: 1, 2, 3, or 4, which corresponds to the most likely generation method of the tree.

sample

8
1 2
1 3
1 4
1 5
1 6
1 7
1 8

1

</p>