Humanity's Last Code Exam / 2021_B / Dungeon Crawler

# Problem Statement

Alice and Bob are in charge of testing a new escape room! In this escape room, customers are trapped in a dungeon and have to explore the entire area. The dungeon consists of n rooms connected by exactly n−1 corridors. It is possible to travel between any pair of rooms using these corridors. 

Two of the dungeon rooms are special. One of these rooms contains a protective idol known as the “helix key.” A different room contains a nasty “dome trap,” which prevents the player from moving once activated. Entering the room with the trap before acquiring the key will result in the player being trapped in the dungeon forever. The player cannot start in the same room as the key or the trap.

There are q different scenarios that Alice and Bob wish to examine. In the i-th scenario, the player starts in room s_(i), the key is in room k_(i), and the trap is in room t_(i). For each scenario, compute the minimum amount of time needed to explore the entire dungeon without getting trapped.

## Input

The first line of input contains two integers n and q, where n (3 ≤ n ≤ 2000) is the number of rooms and q (1 ≤ q ≤ 200000) is the number of scenarios to consider. Rooms are numbered from 1 to n.

The next n−1 lines each contain three integers u, v, and w indicating that there is a corridor between rooms u and v (1 ≤ u,v ≤ n, u≠v) that takes time w (1 ≤ w ≤ 10⁹) to traverse.

Then follow q lines: the i-th of these lines contains three distinct integers s_(i), k_(i), and t_(i) (1 ≤ s_(i),k_(i),t_(i) ≤ n) indicating the room where the player starts, the room with the key, and the room with the trap, respectively.

## Output

For each scenario, output the minimum amount of time needed to visit every room at least once. If it is impossible to visit every room at least once, output "impossible."

## Sample Input 1

# Problem Statement

Alice and Bob are in charge of testing a new escape room! In this escape room, customers are trapped in a dungeon and have to explore the entire area. The dungeon consists of \( n \) rooms connected by exactly \( n-1 \) corridors. It is possible to travel between any pair of rooms using these corridors. 

Two of the dungeon rooms are special. One of these rooms contains a protective idol known as the “helix key.” A different room contains a nasty “dome trap,” which prevents the player from moving once activated. Entering the room with the trap before acquiring the key will result in the player being trapped in the dungeon forever. The player cannot start in the same room as the key or the trap.

There are \( q \) different scenarios that Alice and Bob wish to examine. In the \( i \)-th scenario, the player starts in room \( s_i \), the key is in room \( k_i \), and the trap is in room \( t_i \). For each scenario, compute the minimum amount of time needed to explore the entire dungeon without getting trapped.

## Input

The first line of input contains two integers \( n \) and \( q \), where \( n \) (3 ≤ \( n \) ≤ 2000) is the number of rooms and \( q \) (1 ≤ \( q \) ≤ 200000) is the number of scenarios to consider. Rooms are numbered from 1 to \( n \).

The next \( n - 1 \) lines each contain three integers \( u \), \( v \), and \( w \) indicating that there is a corridor between rooms \( u \) and \( v \) (1 ≤ \( u, v \) ≤ \( n \), \( u \neq v \)) that takes time \( w \) (1 ≤ \( w \) ≤ \( 10^9 \)) to traverse.

Then follow \( q \) lines: the \( i \)-th of these lines contains three distinct integers \( s_i \), \( k_i \), and \( t_i \) (1 ≤ \( s_i, k_i, t_i \) ≤ \( n \)) indicating the room where the player starts, the room with the key, and the room with the trap, respectively.

## Output

For each scenario, output the minimum amount of time needed to visit every room at least once. If it is impossible to visit every room at least once, output "impossible."

## Sample Input 1