Friends
InterviewTime limit1sMemory limit128 MB
Each student points to exactly one friend, forming directed cycles; for each query, report whether two students lie on the same cycle and the forward distance between them.
- Level
Medium6 of 10
- Topics
- Graph, DFS, Implementation, Hash map
- Solved
- No attempts yet
Problem
A school has decided that its students spend too much time studying and not enough time socializing, so it will assign every student a friend.
Friendship is one-directional: if Janet is assigned to be Sarah's friend, Janet must be friendly toward Sarah, but Sarah is not required to feel the same way in return.
Friends are assigned by a computer using student numbers, and every student is assigned exactly one friend. Sometimes this produces a circle of friends. For example, if Marc is assigned Fred, Fred is assigned Lori, Lori is assigned Jean, and Jean is assigned Marc, then Marc, Fred, Lori, and Jean form a circle of four friends.
Within such a circle, the separation from one student to another is the number of friendship steps you must follow to get from the first student to the second, minus one. In the example above, Marc has a separation of from Fred, from Lori, from Jean, and from Marc — to return to Marc you must follow the friendships all the way around the circle.
Given the computer's assignments, for each queried pair of students decide whether both students belong to the same circle of friends, and if so report the separation from the first student to the second.
Input
The first line contains a single integer (), the number of students.
Each of the next lines contains a friendship assignment (, , ), meaning that student is assigned student as a friend (so must be friendly toward ). Every student is assigned exactly one friend.
After the assignments come one or more query lines, each containing two student numbers separated by a single space. For each query you must decide whether the two students belong to the same circle of friends and, if so, their separation. Input ends with a line containing 0 0, which is not a query.
Output
For each query, print on its own line either No if the two students are not in the same circle of friends, or Yes followed by a single space and the separation from the first student to the second if they are.