1import java.util.*;
2
3class Node {
4    int id, p_id;
5    Node(int id, int p_id) { this.id = id; this.p_id = p_id; }
6}
7
8public class TreeNode {
9    public static void classifyNodes(List<Node> nodes) {
10        Map<Integer, Integer> childCount = new HashMap<>();
11        Map<Integer, String> types = new HashMap<>();
12
13        for (Node node : nodes) {
14            if (node.p_id != -1) {
15                childCount.put(node.p_id, childCount.getOrDefault(node.p_id, 0) + 1);
16            }
17            types.put(node.id, "Leaf");
18        }
19
20        for (Node node : nodes) {
21            if (node.p_id == -1) {
22                types.put(node.id, "Root");
23            } else if (childCount.getOrDefault(node.id, 0) > 0) {
24                types.put(node.id, "Inner");
25            }
26        }
27
28        for (Node node : nodes) {
29            System.out.println(node.id + " " + types.get(node.id));
30        }
31    }
32
33    public static void main(String[] args) {
34        List<Node> nodes = Arrays.asList(
35            new Node(1, -1),
36            new Node(2, 1),
37            new Node(3, 1),
38            new Node(4, 2),
39            new Node(5, 2)
40        );
41        classifyNodes(nodes);
42    }
43}