So glad that I was able to solve D by myself after the contest. Too me two wrong attempts and around two hours :)

I used three hash maps:

• One for mapping originalNest -> newNest
• A reverse map for newNest -> originalNest
• Another for tracking pigeon -> originalNest

Here's my submission