Hi everyone. I've been struggling with this for some time now. Any ideas on how to approach this one.

Alice and Bob play a game, Initially, they reside in different cities, in a network of cities having a tree structure. The cities are numbered from 1 to N. Initially Alice resides in city 1, while Bob resides in city N. The game is played in turns with Alice making the first move.

In Alice's turn she will go to any city, adjacent to her current city, which is yet not visited by Alice or Bob and similarly, Bob in his turn will also go to any city not yet visited by him or Alice and is adjacent to his current city. The person who visits the maximum number of cities wins.

Given the N and the connections between cities, predict who wins.

Constraints: 1<=N<=10**5

Example:

N=4 Connections=[{1,2},{2,3},{2,4}]

Output: Alice