The Ties That Guide Us

Now that you have hired an assistant with the profits from your robot sales, you are finally ready to go for the safe that contains the CEOI medals!

The safe is in a university building of $N$ rooms connected by $N - 1$ doors. Every room can be reached from any other room, and each room has at most $3$ doors. You and your assistant each have a floor plan of the building. The two plans show the same layout, but the numbering of the rooms and doors might differ.

During the second competition day, the committee handles clarification requests. This gives you the chance to reach the safe unnoticed.

First, your assistant searches the building. Once he has found the room with the safe, he guides you to it.*

Your assistant leaves secret signs in the rooms. These signs are ties, and the ties are indistinguishable, so the only information you get is the number of ties in a room. The maximum number of ties in any single room should be as small as possible (see the grading section below).

Later, you sneak out during a toilet break and use the ties to find the room with the safe. The safe is hidden, so you cannot recognize it by entering the room. You must rely on the ties you find. Also, your absence must not be noticed, so you should find the safe quickly: you should pass through at most $d + 30$ doors, where $d$ is the number of doors on the direct path from your starting position to the room with the safe. If you pass through a door multiple times, each pass counts.

Write a program that

• tells your assistant how many ties to leave in each room, and
• guides you to the room with the safe afterwards.

* After all, you want to open the safe yourself. It would be no fun to have someone else open it and hand you the medal after the competition!