I've encountered some interesting problems but I couldn't solve them. I really need some help.

**First problem** is: Given 3 integers **N**, **M**, **X** (1 <= **N**, **M** <= 10^{5}, 1 <= **X** <= **M**). Calculate the number of ways to create **N** segments [L_{1}, R_{1}], [L_{2}, R_{2}], …, [L_{N}, R_{N}] (Li <= Hi) such that they satisfy two conditions:

- there is no
*i*and*k*(i != k) that L_{i}<= L_{k}<= H_{k}<= H_{i} - There is at least one segment which has L
_{i}=**X**

*j*such that segment

*j*in two ways are different.

**Second problem**is: Given a tree with 4 nodes 1, 2, 3 and 4. Node 1 is root. Nodes 2, 3 and 4 are leaf nodes.

**Diameter of the tree**is the longest path on the tree. We have

**Q**queries (1 <=

**Q**<= 5 * 10

^{5}). For each query, we are given a leaf node

**v**(1 <= v <=

**N**,

**N**is the number of nodes in the tree). Then we add two new nodes N + 1 and N + 2 to the tree, create two edges (v, N + 1) and (v, N + 2). Output after each query is the diameter of the tree.

Thanks in advance.