408232: GYM103059 M Triforce of Wisdom

A small kingdom in the land of Hyrule is engulfed by chaos when an army led by Ganon, the Prince of Darkness, invaded and stole the Triforce of Power, one part of a magical artifact that alone bestows great strength. In an attempt to prevent him from acquiring the Triforce of Wisdom, Princess Zelda splits it into eight fragments and hides them in secret underground dungeons. Before eventually being kidnapped by Ganon, she commands her nursemaid Impa to find someone courageous enough to save the kingdom. While wandering the land, the old woman is surrounded by Ganon's henchmen, when a young boy named Link appears and rescues her. Upon hearing Impa's plea, he resolves to save Zelda and sets out to reassemble the scattered fragments of the Triforce of Wisdom, with which Ganon can then be defeated.

Three pieces of the Triforce of Wisdom have been scattered in a network of $$$N$$$ dungeons conveniently numbered $$$1\dots N$$$, which are connected by a set of corridors. Each corridor connects two distinct dungeons, and they are arranged in a way such that there is a unique path between each pair of dungeons. Link knows that each dungeon holds at most one piece of the magical item, but he is not sure about which dungeons he should search. Corridors between dungeons are highly unstable and risk collapsing at any time, and exploration could go awry when traveling between dungeons. However, Link is able to buy 'corridor stabilizer' items from shopkeepers; each stabilizer can prevent the collapse of exactly one corridor while Link is still exploring.

A friendly cartographer has helped our hero come up with $$$G$$$ guesses for where the fragments could be in the dungeon network, with the $$$i$$$-th guess expressed as a triple of integers $$$(a_i, b_i, c_i)$$$. If Link can enter into any dungeon in the network to begin his quest, but will only leave the maze once he has collected all three fragments, what is the minimum number of corridor stabilizers Link will need to purchase in order to travel in corridors between dungeons safely? Help the Hero of Hyrule find the optimal solution for each of the $$$G$$$ guesses!

The first line of input contains two integers $$$N$$$ and $$$G$$$ ($$$1 \leq N, G \leq 10^5$$$), representing the number of dungeons in the network and the number of guesses for fragment locations, respectively. The next $$$N-1$$$ lines of input contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq N$$$), which designate endpoint dungeons for a bidirectional corridor. The next $$$G$$$ lines of input contain three distinct integers $$$a_i, b_i, c_i$$$ ($$$1 \leq a_i, b_i, c_i \leq N$$$) that represent dungeons from the $$$i$$$-th guess.

Output $$$G$$$ lines each with a single integer representing the minimum number of corridor stabilizers Link needs to purchase, assuming information from the $$$i$$$-th guess is accurate.

5 3
1 2
2 3
3 5
3 4
3 4 5
1 2 5
1 4 5

2
3
4