Statistics

Problem Statement for "NormalizingTrees"

Problem Statement

Trees are important data structures in programming. In this problem, you will be given a tree that was constructed from a fully connected undirected acyclic graph with exactly N nodes. First, a distinct number between 0 and N-1, inclusive, was assigned to each node. Then, one of the nodes was selected to be the root of the tree. Finally, each non-root node was assigned its neighbor closest to the root as its parent.

You will be given the tree as a int[], where the i-th element is the parent of the i-th node, or -1 if the i-th node is the root (indices are 0-based). A tree is considered equivalent to this tree if it can be constructed from the same original graph using the method described above. This means you can renumber the nodes and select a different node as the root (see examples for clarification). Return a int[] containing the equivalent tree that comes first lexicographically. A int[] a1 comes before int[] a2 lexicographically if a1 has a smaller value at the first element where they differ.

Definition

Class:
NormalizingTrees
Method:
normalize
Parameters:
int[]
Returns:
int[]
Method signature:
int[] normalize(int[] tree)
(be sure your method is public)

Constraints

  • tree will contain between 1 and 50 elements, inclusive.
  • Each element of tree will be between -1 and N-1, inclusive, where N is the number of elements in tree.
  • Exactly one element of tree will be -1.
  • tree will represent a connected acyclic graph.

Examples

  1. {2,0,-1,4,2,4}

    Returns: {-1, 0, 0, 0, 1, 4 }

    This is the original drawing (with 2 as the root): 2 / \ 0 4 / / \ 1 3 5 The renumbering gives this: 1 / \ 4 0 / / \ 5 2 3 and taking the new 0 as the root gives the answer: 0 / | \ 1 2 3 | 4 | 5

  2. {-1,0,1,2,3}

    Returns: {-1, 0, 0, 1, 2 }

    This is a simple path of length 5. Selecting the middle node as root and renumbering gives the lexicographically first representation.

  3. {3,3,3,4,-1,3}

    Returns: {-1, 0, 0, 0, 0, 0 }

    This tree has the shape of a star (one center node with 5 nodes connected to it).

  4. {10,9,6,10,6,9,7,-1,9,7,7,10,6}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 5, 5, 5, 6, 6, 6 }

  5. {-1, 0, 0, 0, 0, 1, 1, 5, 5, 5, 6, 6, 6}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 5, 5, 5, 6, 6, 6 }

  6. {1,-1}

    Returns: {-1, 0 }

  7. {-1}

    Returns: {-1 }

  8. {-1, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24}

    Returns: {-1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 35, 35, 36, 36, 37, 37, 38, 38, 39, 39, 40 }

  9. {43,13,41,29,36,2,17,-1,18,0,3,42,10,5,17,3,42,42,30,24,10,1,41,7,10,47,16,19,8,41,0,40,24,7,29,41,7,3,34,34,38,36,23,42,45,18,3,24,28,36}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 6, 6, 9, 9, 9, 9, 10, 10, 11, 12, 14, 14, 14, 18, 20, 21, 21, 21, 21, 22, 22, 22, 25, 26, 27, 27, 28, 29, 31, 32, 38, 38, 42, 44, 44, 45, 46, 47 }

  10. {7,3,8,14,5,3,3,8,-1,11,3,0,3,19,7,3,14,19,9,2,7}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 8, 8, 8, 11, 12, 14, 15, 16, 16, 17 }

  11. {9,7,-1,2,1,2,11,2,7,2,7,3,1,7}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 6, 7, 11 }

  12. {6,45,27,12,40,15,-1,23,12,11,35,0,19,24,45,10,24,11,30,0,24,14,33,21,6,19,45,24,18,27,6,46,45,12,29,19,13,18,31,30,27,39,49,28,41,36,27,48,7,1}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 6, 7, 8, 10, 10, 11, 11, 12, 13, 16, 16, 16, 17, 17, 18, 18, 19, 20, 20, 20, 20, 22, 22, 22, 23, 27, 29, 30, 31, 34, 37, 40, 41, 43, 44, 47, 48 }

  13. {23,27,32,19,12,27,2,20,12,1,30,32,1,18,6,18,10,7,1,23,30,1,6,30,25,23,2,-1,10,22,1,13,9}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 5, 7, 7, 7, 8, 8, 9, 10, 14, 14, 16, 17, 21, 23, 23, 28, 28, 30 }

  14. {2,35,-1,42,33,40,12,33,7,27,2,10,35,32,3,11,29,2,42,35,24,34,2,42,2,18,42,23,25,42,37,18,2,32,32,36,29,38,25,28,25,22,2,18}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4, 5, 8, 8, 8, 9, 9, 10, 11, 13, 13, 14, 16, 19, 19, 19, 22, 24, 26, 30, 31, 32, 33, 33, 33, 36, 39 }

  15. {8,40,8,19,15,23,15,8,18,47,27,26,17,22,9,19,28,18,-1,47,24,36,9,17,2,39,31,30,47,2,18,9,16,20,48,12,18,24,8,47,39,13,13,17,23,38,37,30,18}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 6, 6, 7, 10, 10, 11, 13, 13, 13, 13, 14, 17, 17, 23, 23, 23, 24, 24, 25, 25, 26, 28, 29, 30, 31, 33, 33, 35, 37, 40, 40, 41 }

  16. {2,13,4,14,11,4,37,38,37,27,27,37,37,43,45,22,44,39,32,25,18,25,23,37,23,24,3,26,23,30,32,43,28,42,23,30,21,-1,28,23,34,11,39,37,21,11,25}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 7, 7, 8, 8, 9, 10, 11, 12, 12, 13, 15, 17, 17, 18, 19, 21, 21, 21, 24, 26, 28, 28, 29, 32, 32, 36, 40, 42, 44, 44 }

  17. {16,23,6,30,30,1,0,12,23,20,30,20,8,5,11,-1,15,4,20,18,15,0,23,20,8,17,30,20,5,0,15}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 4, 7, 7, 8, 10, 10, 10, 10, 11, 14, 16, 16, 17, 21, 21, 21, 25, 26 }

  18. {46,35,12,21,3,44,37,40,23,3,34,34,0,19,33,21,43,18,12,43,16,34,11,0,9,31,46,34,37,46,3,0,8,45,31,41,26,46,28,18,47,26,41,0,47,18,-1,0,36,2}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 8, 10, 10, 10, 10, 12, 12, 12, 13, 14, 15, 16, 17, 18, 19, 19, 20, 21, 23, 23, 24, 27, 36, 40, 40, 40, 43, 45 }

  19. {23,8,30,49,2,41,15,49,6,2,9,26,6,37,21,41,8,20,2,2,41,23,5,30,15,2,32,44,15,25,49,34,41,32,30,9,4,49,26,41,32,49,49,30,25,49,5,32,41,-1}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 5, 8, 8, 8, 8, 9, 14, 14, 18, 18, 24, 24, 24, 24, 24, 25, 25, 26, 31, 31, 33, 33, 34, 34, 35, 38, 43 }

  20. {12,34,20,29,37,29,9,29,20,34,31,7,43,33,24,26,20,34,20,31,34,6,1,1,33,1,37,4,19,24,1,34,25,34,-1,12,34,24,23,29,24,34,33,33}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 9, 9, 9, 9, 10, 13, 14, 21, 23, 24, 24, 24, 24, 25, 25, 28, 28, 33, 37, 38 }

  21. {20,36,39,13,6,36,36,39,39,6,36,1,27,36,36,8,36,34,20,13,36,20,36,36,1,36,32,36,1,39,12,6,6,36,2,36,-1,26,35,36,6}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, 7, 16, 21, 22, 33, 35, 36 }

  22. {33,44,31,9,6,9,41,35,28,-1,9,33,28,21,13,13,28,13,44,31,47,9,21,9,31,31,31,41,9,9,23,41,31,41,7,31,28,41,31,9,45,9,41,35,9,21,41,9,44}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 6, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 14, 23, 23, 23, 24, 31, 31, 46 }

  23. {11,0,4,5,7,11,11,11,11,11,11,-1,9,11,4}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 9, 9 }

  24. {11,3,32,11,11,32,32,11,26,20,11,-1,4,20,3,24,20,3,11,11,24,7,4,11,18,5,18,26,26,4,17,20,18,18}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 9, 9, 9, 10, 10, 10, 11, 11, 13, 20, 26, 26, 26, 26 }

  25. {28,28,7,28,1,15,22,1,28,1,7,35,22,17,17,35,27,22,28,17,35,1,-1,22,22,7,41,28,22,12,27,35,17,22,27,17,17,41,43,22,17,43,22,22,17,43,22,43,27,22}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 13, 13, 13, 13, 21, 21, 21, 21, 22, 22, 22, 22, 27, 27, 32, 36, 36, 36 }

  26. {44,0,0,1,33,10,33,13,39,13,14,41,40,16,24,44,31,25,8,43,41,16,25,39,46,4,24,31,31,-1,29,29,12,13,0,46,44,45,11,35,4,12,9,8,28,33,28,25,43,29}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 5, 5, 6, 8, 8, 8, 9, 11, 11, 11, 17, 17, 18, 18, 19, 19, 21, 21, 23, 23, 23, 24, 24, 27, 29, 29, 29, 32, 32, 33, 35, 38, 40, 40, 42, 43, 43, 46, 46 }

  27. {12,10,30,35,31,31,3,28,6,-1,26,17,26,25,21,3,10,2,11,5,25,20,10,9,21,5,31,15,16,30,23,23,11,23,19,30,2}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 5, 5, 6, 6, 8, 8, 9, 11, 11, 11, 12, 13, 13, 14, 15, 17, 17, 18, 22, 25, 25, 26, 27, 28, 29, 29 }

  28. {12,12,15,5,16,8,10,14,12,18,18,8,15,12,-1,7,2,9,12,17}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 7, 8, 9, 10, 11, 13, 15 }

  29. {29,45,23,9,35,27,13,27,26,1,14,41,47,-1,7,26,40,4,40,5,17,30,42,6,33,44,38,31,15,17,23,6,41,27,26,46,21,26,4,24,10,43,5,27,6,29,42,24,4}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 2, 3, 4, 5, 6, 6, 8, 8, 8, 9, 9, 10, 10, 11, 12, 14, 14, 15, 17, 21, 22, 23, 27, 27, 28, 28, 28, 29, 32, 32, 33, 36, 36, 38, 38, 38, 38, 39, 41, 45, 47 }

  30. {3,9,1,4,2,-1,4,6,5,8}

    Returns: {-1, 0, 0, 0, 1, 2, 3, 4, 7, 8 }

  31. {28,24,17,20,30,32,32,9,15,22,27,32,26,14,-1,9,35,4,31,11,9,6,24,30,13,1,25,20,23,13,18,35,25,25,12,13}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 1, 2, 3, 5, 6, 8, 8, 9, 12, 12, 12, 13, 15, 15, 18, 18, 18, 19, 21, 21, 22, 24, 25, 28, 28, 30, 31, 32, 33 }

  32. {33,22,4,14,36,7,48,40,32,20,20,39,14,20,25,27,35,31,48,45,14,22,4,5,1,2,5,14,48,49,25,25,37,27,42,40,-1,24,15,44,14,5,8,9,6,28,12,38,1,46}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 7, 8, 10, 13, 14, 15, 16, 17, 18, 18, 21, 21, 21, 23, 25, 26, 26, 33, 33, 35, 35, 35, 36, 37, 38, 40, 41, 42, 43, 44, 46, 48 }

  33. {6,37,6,6,6,37,-1,6,6,6,37,6,6,37,6,0,6,37,6,6,6,6,6,6,37,6,37,6,37,37,6,6,6,37,6,6,37,6,37,6,6,37,6,37,6,37,6,6,6,30}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3 }

  34. {16,23,10,16,16,16,16,23,23,16,27,23,16,16,16,23,-1,16,16,34,16,23,16,16,16,23,16,29,16,23,16,16,23,16,23}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 21, 22, 31, 33 }

  35. {21,8,12,45,19,-1,5,30,16,30,43,37,45,47,6,43,47,5,0,27,7,8,20,3,5,41,29,38,14,4,34,41,17,0,13,33,18,46,14,25,7,17,2,12,4,27,21,32,40,44}

    Returns: {-1, 0, 0, 0, 1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 12, 12, 13, 13, 14, 15, 16, 20, 20, 21, 21, 23, 23, 24, 25, 27, 27, 29, 30, 31, 31, 32, 33, 33, 35, 35, 36, 36, 37, 38, 38, 40, 41, 42, 43, 44 }

  36. {33,6,26,2,1,10,22,43,9,14,38,39,9,45,18,11,42,7,23,33,24,3,35,-1,1,13,35,47,2,11,34,3,29,23,42,8,25,34,12,10,23,25,39,23,22,6,7,26}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 2, 3, 7, 7, 8, 11, 11, 12, 13, 14, 14, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 21, 21, 23, 23, 25, 25, 28, 28, 29, 30, 30, 31, 31, 34, 36, 37, 37, 39, 42, 42 }

  37. {5,4,0,6,3,6,-1,4,6,7,6,3,0,7,11}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 2, 5, 5, 6, 7, 7, 8, 8 }

  38. {34,7,10,5,14,21,28,41,20,27,47,8,24,29,3,34,19,15,49,47,4,13,31,42,2,2,19,32,9,1,20,38,5,0,4,45,0,13,47,8,7,35,49,24,15,12,18,-1,12,9}

    Returns: {-1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 10, 10, 12, 15, 15, 16, 17, 18, 18, 19, 20, 22, 22, 23, 24, 24, 25, 26, 26, 27, 28, 30, 34, 35, 36, 36, 37, 37, 39, 39, 41, 43, 43, 44, 44, 45, 48 }

  39. {7,24,30,20,25,9,31,31,24,11,17,22,20,28,5,23,29,15,0,29,28,30,-1,2,32,5,0,18,10,3,8,22,27}

    Returns: {-1, 0, 0, 0, 1, 1, 2, 4, 6, 6, 7, 10, 11, 12, 13, 13, 14, 16, 16, 17, 19, 20, 21, 21, 22, 24, 24, 25, 27, 28, 29, 29, 30 }

  40. {28,12,17,11,17,16,7,21,26,23,0,28,19,26,34,5,9,27,31,27,9,33,30,3,14,10,7,33,32,22,18,20,19,-1,0,11}

    Returns: {-1, 0, 0, 0, 1, 1, 2, 2, 3, 4, 5, 6, 8, 8, 9, 11, 12, 12, 13, 15, 15, 16, 16, 17, 19, 20, 23, 24, 25, 26, 26, 27, 29, 29, 31, 34 }

  41. {10,44,17,31,47,35,46,39,28,16,42,38,21,2,18,33,20,20,21,11,35,-1,36,46,34,15,1,42,1,27,10,5,38,23,33,21,47,43,15,8,2,19,28,4,37,39,31,41,21}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 2, 5, 5, 6, 8, 9, 10, 10, 11, 11, 13, 13, 17, 19, 19, 20, 20, 21, 22, 22, 25, 27, 28, 29, 29, 30, 31, 32, 34, 35, 36, 36, 37, 37, 39, 39, 40, 41, 41, 42, 43, 43 }

  42. {4,6,5,2,1,8,-1,5,0,6}

    Returns: {-1, 0, 0, 0, 1, 2, 4, 6, 7, 8 }

  43. {8,26,3,13,11,8,9,5,10,16,29,22,20,19,21,20,23,26,12,4,7,-1,24,27,21,27,7,18,6,2}

    Returns: {-1, 0, 0, 0, 1, 1, 2, 2, 3, 4, 8, 8, 9, 10, 12, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 27, 28 }

  44. {21,21,1,25,20,46,22,4,42,34,43,25,18,40,43,44,7,21,48,33,32,-1,47,40,39,21,8,21,29,17,24,8,9,29,31,7,5,1,24,18,6,27,41,20,27,28,48,9,26,14}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 6, 7, 12, 12, 13, 15, 16, 17, 17, 20, 21, 22, 22, 23, 24, 24, 25, 26, 26, 27, 29, 30, 31, 32, 32, 34, 34, 35, 38, 38, 39, 40, 41, 43, 43, 44, 44 }

  45. {13,29,1,29,8,15,1,34,17,32,42,38,41,-1,34,9,31,37,41,41,16,38,38,42,15,17,29,34,42,13,2,1,13,37,17,36,13,36,17,13,15,1,31,33,33,2,2,25,36,38}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 13, 13, 13, 14, 14, 17, 17, 17, 17, 22, 22, 22, 23, 26, 26, 26, 26, 29, 30, 30, 30, 31, 31, 31, 32, 32, 34, 34, 34, 41, 41, 41, 42 }

  46. {-1,0,4,5,0,0,0,0,5}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 2 }

  47. {11,15,9,15,12,10,8,8,5,14,-1,5,10,11,12,14,5}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 2, 2, 3, 9, 9, 10, 10, 12, 12, 13 }

  48. {35,48,37,32,37,37,35,2,22,37,31,33,30,46,37,44,22,13,24,22,21,5,5,32,2,7,9,17,35,21,13,5,13,13,32,14,48,-1,24,2,7,21,30,21,9,30,37,48,9}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 5, 7, 7, 7, 7, 8, 8, 8, 9, 10, 10, 10, 11, 13, 13, 14, 14, 16, 16, 16, 16, 17, 17, 17, 34, 34, 34, 35, 35, 35, 36, 37 }

  49. {41,27,31,24,18,3,18,6,39,44,44,15,31,39,31,24,12,2,-1,6,3,15,36,27,18,4,35,24,6,6,14,18,44,14,3,24,31,12,44,4,15,4,2,35,18,39,4,27,36,35}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 11, 14, 14, 15, 15, 16, 16, 17, 17 }

  50. {27,7,5,7,27,-1,22,26,27,23,6,16,2,16,6,22,26,5,15,25,15,25,5,2,25,17,5,17}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11 }

  51. {1,20,30,30,5,29,21,5,31,20,14,-1,21,29,29,2,3,31,13,14,30,30,1,21,20,3,13,21,2,11,11,29,1,2,2,20,3,13,3,14,5,31}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 6, 6, 22, 22, 22, 22, 26, 26, 26, 27, 27, 27, 28, 28, 28, 29, 29, 29 }

  52. {24,33,3,19,12,25,34,2,12,27,41,16,45,12,15,19,15,27,2,-1,25,27,12,19,23,3,41,45,41,41,34,19,14,31,23,33,14,34,24,27,16,31,34,24,25,19,33,2,33}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 15, 15 }

  53. {22,31,23,19,12,12,20,14,39,-1,20,27,24,14,24,39,49,27,49,9,31,49,24,9,9,22,49,31,39,27,14,9,23,12,12,22,19,20,20,31,27,22,23,14,19,23,1,39,19,24}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 28 }

  54. {15,14,25,15,30,41,25,15,15,20,6,5,37,14,41,17,37,34,20,30,41,25,40,5,14,-1,43,43,40,5,37,40,40,43,10,20,14,17,5,20,37,17,43,41}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 22, 22, 22, 22, 23, 23, 23, 23, 24, 25, 25, 25, 25, 26, 26, 33, 40, 41, 41 }

  55. {34,24,32,35,8,14,34,32,14,22,5,35,16,1,15,37,15,34,1,8,22,22,24,14,37,32,16,22,16,8,32,35,24,1,37,15,1,-1}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 17, 17, 17, 18, 18, 18, 19, 19, 19, 20, 20, 20, 21, 21, 21, 25, 25, 25, 26 }

  56. {9,31,15,21,0,29,22,10,9,12,38,23,37,29,10,8,31,0,44,8,22,9,8,38,15,31,44,8,21,38,23,38,10,0,0,44,15,44,9,10,23,23,21,29,-1,31,15,21,29}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 26, 26, 26, 26, 27, 27, 38, 45, 45, 45 }

  57. {8,31,41,47,8,42,8,14,19,13,31,14,34,34,-1,10,42,47,41,33,31,41,42,10,41,10,34,44,20,47,20,29,20,44,37,44,14,14,47,42,34,19,19,44,9,20,31,19,10,8}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 22, 22, 22, 22, 23, 23, 23, 23, 24, 28, 28, 28, 28, 29, 29, 29, 29, 32, 41, 41, 41, 41, 42, 46, 46, 46 }

  58. {31,12,21,40,42,35,9,42,13,32,13,12,21,32,13,2,31,12,31,13,35,22,26,40,9,35,9,42,12,40,35,32,38,2,42,32,2,2,3,31,-1,21,21,9}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 22, 23, 24, 24, 25, 25, 25, 25, 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30 }

  59. {3,0,3,-1}

    Returns: {-1, 0, 0, 1 }

  60. {32,14,34,25,25,1,9,25,29,14,9,20,16,9,37,29,1,32,34,21,14,14,31,16,16,37,20,9,34,1,20,5,1,32,5,29,5,-1,21,21,20,25,34,32,5,31,16,21,29}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 10, 10, 10, 10, 11, 11, 38, 38, 38, 38 }

  61. {29,22,25,30,25,30,35,43,9,35,22,34,34,30,16,35,0,37,30,43,16,9,0,43,9,0,16,43,37,12,35,16,22,22,-1,0,0,25,9,22,16,37,30,35,37,9,37,43,25,25}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 12, 12, 12, 12, 12, 27, 48 }

  62. {10,7,1,18,1,2,18,0,2,18,-1,10,1,2,1,2,18,1,2}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 7, 16, 17 }

  63. {14,18,20,18,39,33,5,25,18,5,18,39,39,20,33,14,18,14,25,25,23,33,5,-1,39,23,20,39,20,33,25,25,20,23,5,14,19,5,14,33}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 25 }

  64. {41,-1,19,41,20,23,23,27,20,23,1,18,2,15,1,19,1,12,2,1,2,18,23,19,27,41,20,2,27,18,41,18,15,27,15,12,23,41,19,12,15,2,15,20,20,18,12,19,12}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9 }

  65. {9,48,36,48,20,4,18,48,46,20,17,1,18,12,1,23,42,6,23,12,6,9,28,28,13,20,12,9,-1,4,42,25,4,6,17,7,13,25,28,25,1,7,17,7,46,42,18,13,46,23}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 8, 8, 8, 11, 11, 11, 14, 14, 17, 17, 17, 18, 18, 18, 19, 19, 19, 20, 20, 20, 23, 23, 23, 24, 24, 24, 26 }

  66. {17,17,0,1,13,13,10,14,0,14,9,0,10,9,1,14,15,-1,15,15,1,13,9,10,17}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 5, 5, 5, 6, 6, 6, 8, 8, 20, 20, 20 }

  67. {7,5,5,2,5,7,2,-1,2}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 1, 2 }

  68. {3,12,29,33,14,3,12,30,30,13,22,16,16,40,6,16,29,13,46,37,40,14,33,14,22,30,22,35,46,39,40,13,11,37,37,-1,46,29,35,44,33,6,3,11,45,38,12,11,6}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 8, 8, 8, 23, 23, 23, 24, 26, 26, 26, 27, 27, 27, 29, 30, 30, 30, 31, 31, 31, 36, 37, 37, 37, 43, 47 }

  69. {27,35,22,38,21,36,40,11,21,38,35,36,5,23,27,38,0,0,31,22,38,13,31,40,32,14,5,23,18,21,14,6,40,38,0,32,6,0,13,0,-1,18,14,14,14,24,24,21,21,11}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 7, 7, 7, 7, 7, 8, 8, 14, 14, 15, 15, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 18, 18, 19, 19, 30, 30, 31, 31, 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 37, 37 }

  70. {2,9,7,10,7,2,10,1,10,10,-1,2}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 5, 7, 8, 8, 8 }

  71. {7,7,4,-1,14,12,9,13,11,14,12,17,17,3,3,13,9,3,11,4}

    Returns: {-1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8 }

  72. {30,5,34,6,34,28,35,41,44,17,7,31,14,14,47,7,23,2,6,25,40,44,47,4,31,27,7,-1,27,41,19,19,40,30,27,27,7,42,42,17,4,28,35,5,2,22,22,25,23}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 6, 6, 8, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28 }

  73. {45,18,12,24,30,29,36,24,29,36,24,27,45,36,26,44,30,0,-1,29,0,26,44,30,45,27,45,1,40,18,1,26,29,24,44,40,18,36,44,26,1,0,27,30,1,18,40,0,27,40}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 28 }

  74. {3,3,4,-1,3,3}

    Returns: {-1, 0, 0, 0, 0, 1 }

  75. {8,7,5,7,8,-1,8,5,5}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 5, 5 }

  76. {37,32,43,40,19,43,13,43,15,15,32,42,37,4,43,19,42,47,42,-1,47,37,13,47,13,32,40,40,47,13,42,13,4,15,43,40,47,4,37,32,4,42,15,15,37,40,8,4,32}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 32, 32, 32, 32, 32, 33, 33, 33, 33, 33, 34, 34, 34, 34, 34, 35 }

  77. {4,-1,1,16,35,14,2,8,35,41,25,14,2,8,35,16,35,14,20,20,35,41,41,41,16,1,8,8,4,41,8,25,2,4,14,1,16,14,20,25,4,1,25,20,4,2,25,16,2,20}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 32, 32, 32, 32, 32, 33, 33, 33, 33, 33, 34, 34, 34, 34, 34 }

  78. {6,6,12,12,12,-1,5,0,6,12,0,6,5}

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 2, 8, 8, 8, 8 }

  79. {2,2,-1}

    Returns: {-1, 0, 0 }

  80. {28,28,-1,27,48,27,18,2,23,32,23,46,32,18,18,32,38,46,33,38,38,46,36,33,46,23,9,7,33,36,36,38,7,2,48,28,32,48,7,27,27,18,48,36,28,36,33,23,7}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 7, 7, 7, 7, 8, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31, 32, 32, 32, 32 }

  81. {19,5,49,36,15,44,8,18,44,22,8,15,36,21,1,41,47,6,11,11,49,41,4,19,46,22,18,43,38,7,38,6,13,10,26,10,5,43,32,1,13,-1,47,40,21,46,4,40,26,32}

    Returns: {-1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 35, 35, 36, 36, 37, 37, 38, 38, 39, 39, 40 }

  82. {13,5,8,18,9,6,-1,19,15,17,19,13,9,5,1,6,1,15,8,17}

    Returns: {-1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 10, 12, 12, 14, 14, 15, 15 }

  83. {3,4,3,1,-1,13,18,4,7,13,8,17,17,15,8,7,18,15,1,10}

    Returns: {-1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 10, 12, 12, 14, 14, 15, 15 }

  84. {36,47,33,12,3,14,20,27,48,17,43,44,19,6,11,3,32,47,25,33,41,20,1,6,30,28,30,12,41,32,28,21,38,-1,25,43,1,17,44,14,36,2,48,11,2,21,27,19,38}

    Returns: {-1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 35, 35, 36, 36, 37, 37, 38, 38, 39, 39 }

  85. {13,27,-1,16,29,44,15,27,30,2,9,22,45,33,4,39,10,4,9,15,41,30,29,31,45,41,16,39,0,32,10,18,2,2,31,16,13,44,33,32,0,10,22,38,13,18,38,4,30,41}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 20, 21, 21, 22, 22, 23, 23, 28, 28, 29, 29, 33, 33, 33, 34, 34, 35, 35, 36, 36 }

  86. {2,7,7,2,1,1,1,-1,7}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 5, 5 }

  87. {17,0,15,14,17,0,27,28,7,26,0,4,15,26,28,14,21,28,4,15,3,17,21,4,7,3,14,7,-1}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 11, 11, 11, 12, 12, 12, 15, 15, 15, 16, 16, 17, 17, 18 }

  88. {21,25,17,24,17,21,26,40,34,18,42,46,13,45,45,33,25,36,26,9,42,24,47,40,26,18,-1,14,17,34,11,13,42,3,3,9,24,21,33,14,46,11,45,13,40,6,6,36,9}

    Returns: {-1, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 11, 11, 12, 12, 15, 15, 15, 16, 16, 17, 17, 17, 18, 18, 19, 19, 19, 20, 20, 21, 21, 22, 22, 22, 23, 23, 32, 32, 32, 33, 34, 34, 35, 35 }

  89. {10,13,21,37,14,18,45,13,21,37,28,28,18,47,28,13,28,14,28,11,37,47,21,13,37,11,14,21,47,11,14,10,16,11,10,10,18,47,18,45,16,18,10,14,21,47,45,-1,13,45}

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25 }

  90. {10, 9, 6, 10, 6, 9, 7, -1, 9, 7, 7, 10, 6 }

    Returns: {-1, 0, 0, 0, 0, 1, 1, 5, 5, 5, 6, 6, 6 }

  91. {-1, 0, 0, 0, 3, 3, 1, 3, 4, 6, 1, 8, 7, 0, 11, 8, 6, 11, 0, 5, 16, 17, 8, 2, 21, 7, 18, 26, 27, 16, 25, 12, 26, 21, 0, 24, 3, 8, 34, 22, 2, 5, 39, 34, 23, 14, 1, 13, 20, 23 }

    Returns: {-1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 6, 7, 7, 8, 8, 9, 11, 11, 14, 14, 18, 18, 20, 21, 24, 24, 24, 24, 25, 25, 29, 33, 33, 34, 37, 40, 41, 42, 44, 44, 47 }

  92. {12, 23, 0, 15, 5, 12, 7, 0, 11, 20, 1, 23, -1, 12, 13, 13, 3, 3, 2, 24, 22, 20, 5, 12, 2, 15, 12, 26, 26 }

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 8, 8, 10, 11, 12, 16, 19, 19, 23, 23 }

  93. {-1, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 6, 6, 7, 7, 7, 8, 8, 9, 10, 11, 11, 12, 12, 12 }

    Returns: {-1, 0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 8, 8, 8, 9, 9, 9, 13, 13, 13, 14, 14, 15, 16, 16, 17, 17, 18 }

  94. {-1, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 13, 13, 10 }

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 6, 6, 7, 8, 8, 9, 11, 11, 12, 12, 13, 13, 18, 18, 19, 19, 20, 20, 20, 21, 21, 22, 22, 23, 23 }

  95. {-1, 0, 0, 0, 1, 2, 2, 4, 3, 7 }

    Returns: {-1, 0, 0, 0, 1, 1, 2, 3, 6, 8 }

  96. {12, 4, 9, 9, 5, 8, 7, 8, -1, 5, 9, 4, 7 }

    Returns: {-1, 0, 0, 0, 0, 1, 1, 5, 5, 6, 9, 9, 10 }

  97. {-1, 0, 1, 1, 3 }

    Returns: {-1, 0, 0, 0, 1 }

  98. {3, 2, 3, 4, -1, 4, 1, 2, 0, 0, 12, 12, 5, 5, 13, 13 }

    Returns: {-1, 0, 0, 0, 1, 1, 2, 2, 3, 4, 8, 8, 10, 10, 11, 11 }

  99. {-1, 0, 1, 2, 3, 0, 2, 5, 4, 4, 6, 7, 7, 9, 2, 14, 5, 14, 15, 15, 3, 2, 18, 21, 9, 7, 22, 17, 25, 12, 20, 28, 24, 12, 19, 31, 35, 1, 3, 14, 21, 12, 27, 23, 10, 0, 28, 31, 39, 0 }

    Returns: {-1, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9, 10, 12, 12, 12, 14, 16, 17, 18, 19, 21, 21, 24, 24, 29, 32, 34, 34, 34, 38, 38, 38, 39, 44, 44, 45, 45, 47 }

  100. {-1, 0, 0, 1, 1, 2, 2, 3, 3, 5, 5, 6, 7, 7, 8, 8, 0, 0, 0, 0, 0, 0 }

    Returns: {-1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 9, 9, 10, 11, 11, 16, 16, 17, 17 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: