I'm having trouble understanding the statement of problem D of the Nikkei contest (https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_d?lang=en). It says that the original tree is unique, but for the first sample case, the original tree can also be 1 -> 2 and 1 -> 3, right?
Please note that the extra M edges always extends from a vertex u to its "descendant" v.