This page is still under construction.

Parts of this page are still being built. What you see may change.

Friends

Interview

Time limit1sMemory limit128 MB

Summary
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 00 from Fred, 11 from Lori, 22 from Jean, and 33 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 nn (2≤n≤99992 \le n \le 9999), the number of students.

Each of the next nn lines contains a friendship assignment x yx\ y (1≤x≤99991 \le x \le 9999, 1≤y≤99991 \le y \le 9999, x≠yx \ne y), meaning that student xx is assigned student yy as a friend (so xx must be friendly toward yy). 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.

Examples1

  1. Example 1

    Input
    6
    1 2
    2 3
    3 1
    10 11
    100 10
    11 100
    1 100
    2 3
    0 0
    
    Expected output
    No
    Yes 0