This page is still under construction.

Parts of this page are still being built. What you see may change.

Nested Set Model

Interview

Time limit1sMemory limit1024 MB

Summary
Root an undirected tree at S, traverse children in ascending order, and label each node with nested left/right interval numbers.
Level

Medium6 of 10

Topics
DFS, Tree, Graph, Recursion
Solved
No attempts yet

Problem

SQL is excellent at expressing data that can be represented as relations, but it is limited when it comes to expressing hierarchical structures. The nested set model is one of the models introduced to make up for this limitation.

The nested set model represents hierarchical structures using the containment relation between intervals, and any two pieces of data either do not overlap or one contains the other. The nested set model assigns numbers to the left and right fields of each node in a tree according to the order in which the tree is visited, so that the left and right fields represent an interval. For each node, left < right is guaranteed.

For nodes A and B in a nested set model, if A.left < B.left and B.right < A.right, then A contains B. To retrieve all nodes that node A contains, run the SQL command SELECT * FROM tree WHERE left > A.left AND right < A.right;.

For example, suppose we are representing the organization chart of a company. The company HI-ARC has several departments, and each department can have several teams. Each team can contain several employees.

Suppose the organization is structured as follows.

Level 1

  • HI-ARC - (Management Support Office, Development Department)

Level 2

  • Management Support Office - (Business Strategy Team, Legal Team)
  • Development Department - (Development Team 1, Development Team 2, Operations Team)

Level 3

  • Business Strategy Team - Employee 1, Employee 2
  • Legal Team - Employee 3
  • Development Team 1 - Employee 4, Employee 5
  • Development Team 2 - Employee 6, Employee 7, Employee 8
  • Operations Team - Employee 9

Then the organization above can be represented as a nested set model as follows.

Department/Nameleftrightlevel
HI-ARC1341
Management Support Office2132
Business Strategy Team383
Employee 1454
Employee 2674
Legal Team9123
Employee 310114
Development Department14332
Development Team 115203
Employee 416174
Employee 518194
Development Team 221283
Employee 622234
Employee 724254
Employee 826274
Operations Team29323
Employee 930314

Given an arbitrary acyclic graph, choose one node as the root and output the left and right fields of each node when the resulting tree is represented as a nested set model.

Input

The first line gives the number of vertices N in the tree (2 ≤ N ≤ 105).

Lines 2 through N + 1 give information about the edges connected to each vertex. Each line starts with the number Vi (1 ≤ Vi ≤ N) of the vertex the edges are connected to, and until -1 is read, information about all nodes connected to that node follows.

Line N + 2 gives the number S of the vertex that will serve as the root node.

Here, the edges of the tree are given as input like the edges of a directed graph, but the input is guaranteed to be that of an undirected graph. If the edge from node 2 to node 3 is given as input, then when the information for node 3's connected nodes is given, the edge from node 3 to node 2 appears in the input.

Because the information of the tree's undirected edges is given, the total number of edges is 2 × (N - 1), and every vertex is directly or indirectly connected to every other through edges.

Output

When node S is the root, output the left field and right field of each node after building the nested set by visiting nodes in ascending order, starting from the smallest number.

Output the number of node i and its left / right fields on line i, across N lines total.

Here, every output left field and right field is a distinct natural number between 1 and 2 × N inclusive.

Examples1

  1. Example 1

    Input
    3
2 1 3 -1
3 2 -1
1 2 -1
2
    Expected output
    1 2 3
2 1 6
3 4 5