Consider the minimum value of \(\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace\) in which \(\big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N) \big)\) satisfies the conditions in the Problem Statement.

For a given tree, let \(M\) be the number of leaves (vertices without children), and \(v_1, v_2, \ldots, v_M\) be the \(M\) leaves. Then,

for any pair of distinct leaves \((v_i, v_j)\), it holds that \(S_{v_i} \cap S_{v_j} = \lbrace v_i \rbrace \cap \lbrace v_j \rbrace = \emptyset\),

so, by the condition in the Problem Statement, it should be that

for any pair of distinct leaves \((v_i, v_j)\), it holds that \([L_{v_i}, R_{v_i}] \cap [L_{v_j}, R_{v_j}] = \emptyset\).

Thus, \(\lbrace L_{v_1}, L_{v_2}, \ldots, L_{v_M} \rbrace\) should contain at least \(M\) distinct positive integers (same holds for \(\lbrace R_{v_1}, R_{v_2}, \ldots, R_{v_M} \rbrace\)). Therefore, the minimum value of \(\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace\) that can be achieved is at least \(M\).

Conversely, \(\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace = M\) can be achieved. Indeed, we can construct \(\big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N) \big)\) achieving \(\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace = M\) as follows.

1. First, perform Depth-First Search (DFS) from the root, Vertex \(1\). For each of \(M\) leaves, give it a nickname of Leaf \(1\), Leaf \(2\), \(\ldots\), Leaf \(M\), in the order of visiting during the DFS.

2. For each \(i =1, 2, \ldots, N\), let \(L_i\) and \(R_i\) be the minimum and maximum value of the nicknames of the leaves included in the subtree rooted at Vertex \(i\).

Finding the minimum and maximum value of the nicknames of the leaves included in the subtree rooted at Vertex \(i\) in Step 2. can be achieved in a total of \(O(N)\) time with DFS.

Since the nicknames of the leaves was given in the DFS, for each \(i = 1, 2, \ldots, N\), the set of nicknames of leaves in the subtree rooted at Vertex \(i\) is a set of consecutive integers. Therefore, the set of nicknames of leaves in the subtree rooted at Vertex \(i\) is \([L_i, R_i]\). Moreover, the nicknames of leaves are pairwise distinct, so \(\big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N) \big)\) constructed by the procedure above indeed satisfies the condition in the Problem Statement.

Hence, the problem can be solved in a total of \(\mathrm{O}(N)\) time.

The following is a sample code in C++.

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> G[200005];
int L[200005], R[200005];
int leaf[200005];

int id = 0;
void dfs(int v, int p)
{
  if(v != 1 && G[v].size() == 1){
    leaf[v] = ++id;
    return;
  }
  for(auto u : G[v]) if(u != p) dfs(u, v);
}

void dfs2(int v, int p)
{
  if(leaf[v]){
    L[v] = R[v] = leaf[v];
    return;
  }
  L[v] = 1e9, R[v] = -1e9;
  for(auto u : G[v]){
    if(u == p) continue;
    dfs2(u, v);
    L[v] = min(L[v], L[u]);
    R[v] = max(R[v], R[u]);
  } 
}

int main(void)
{
  cin >> n;
  int u, v;
  for(int i = 1; i <= n-1; i++){
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  
  dfs(1, -1);
  dfs2(1, -1);
  for(int i = 1; i <= n; i++) cout << L[i] << " " << R[i] << "\n";
  
  return 0;
}