Degrees of Separation

Time limit1sMemory limit128 MB

Summary

Maintain a friendship graph under edge insertions and deletions, and answer queries about friend counts, friends-of-friends counts, and shortest-path distance between two people.

Level: Medium5 of 10
Topics: Graph, BFS, Hash map, Implementation
Solved: No attempts yet

Problem

A popular way for people to stay connected is through a social network. One interesting question you can ask about such a network is the degree of separation between two people: the number of friendships on the shortest chain that links them.

For example, in the network shown below there are many chains between Abby and Alberto, such as:

Abby → Zoey → Alberto
Abby → Natalie → Zoey → Alberto
Abby → George → Ali → Kara → Ricardo → Jeff → Alberto

The shortest chain from Abby to Alberto uses two friendships (Abby–Zoey and Zoey–Alberto), so their degree of separation is 2, and Alberto is a friend of a friend of Abby.

Your program begins from the fixed set of friendships listed below and then processes a sequence of commands. Friendships can begin (sometimes introducing brand-new people) and can end over time. You must be able to report how many friends a person has, how many friends of friends they have, and the degree of separation between any two people.

Initial Friendships

Every person has an integer id, shown in parentheses.

id	Name	id	Name	id	Name
1	Chris	7	George	13	Jeff
2	Bruce	8	Ali	14	Terry
3	Zoey	9	Kara	15	Alberto
4	Stephen	10	Nomar	16	Kim
5	Natalie	11	Siobahn	17	Richard
6	Abby	12	Ricardo	18	Trevor

The network starts with exactly these mutual friendships, written as id pairs a-b:

1-6, 2-6, 3-4, 3-5, 3-6, 3-15, 4-5, 4-6, 5-6, 6-7, 7-8, 8-9, 9-10, 9-12, 10-11, 11-12, 12-13, 13-14, 13-15, 16-17, 16-18, 17-18

Initial friendship network

Input

Each command appears on its own line. a and b are person ids.

Command	Meaning
`i a b`	Person `a` and person `b` become friends. Either one may be a brand-new person. If they are already friends, nothing changes.
`d a b`	Person `a` and person `b` stop being friends. If they were not friends, nothing changes.
`n a`	Report how many friends person `a` currently has.
`f a`	Report how many friends of friends person `a` has.
`s a b`	Report the degree of separation between person `a` and person `b`.
`q`	Stop processing. This is always the final command.

Definitions:

The friends of friends of a is the number of distinct people who are a friend of at least one of a's friends, not counting a and not counting a's own direct friends.
The degree of separation between a and b is the number of friendships on the shortest chain connecting them. It is 0 when a and b are the same person.

Output

For every n, f, and s command, print the requested value on its own line, in the order the commands are given.

For an s command, print Not connected (exactly, without quotes) when no chain of friendships connects the two people.

Constraints

Every id is an integer between 1 and 1,000,000.
There are at most 100,000 commands, and the input always ends with a single q.
Every friendship is mutual.

Examples1

Example 1

Input

Expected output

2
3
4