Farmer John is planning to build N (1 \leq N \leq 10^5) farms that will be connected by N-1 roads, forming a tree (i.e., all farms are reachable from each-other, and there are no cycles). Each farm contains a cow, whose breed is either Guernsey or Holstein.

Farmer John's M friends (1 \leq M \leq 10^5) often come to visit him. During a visit with friend i, Farmer John will walk with his friend along the unique path of roads from farm A_i to farm B_i (it may be the case that A_i = B_i). Additionally, they can try some milk from any cow along the path they walk. Since most of Farmer John's friends are also farmers, they have very strong preferences regarding milk. Some of his friends will only drink Guernsey milk, while the remainder will only drink Holstein milk. Any of Farmer John's friends will only be happy if they can drink their preferred type of milk during their visit.

Please determine whether each friend will be happy after visiting.

SCORING:

Test cases 2-5 satisfy N\le 10^3, M\le 2\cdot 10^3.

Problem credits: Spencer Compton

#4137 upload 2 done 2 how_to_reg 2

Milk Visits timer 1s memory 512MB

#4137

Milk Visits 1s 512MB