친구 사이의 분리 차수

시간 제한1초메모리 제한128 MB

요약

친구 관계를 추가하고 삭제하면서 한 사람의 친구 수, 친구의 친구 수, 두 사람 사이의 최단 거리를 구하는 문제입니다.

난이도: 보통10점 중 5점
유형: 그래프, BFS, 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

사람들이 서로 연결되는 대표적인 방법은 소셜 네트워크입니다. 이런 네트워크에서 던질 수 있는 흥미로운 질문 중 하나는 두 사람 사이의 분리 차수(degree of separation), 즉 두 사람을 잇는 가장 짧은 친구 관계 사슬에 들어 있는 친구 관계의 수입니다.

예를 들어 아래 네트워크에서 Abby와 Alberto를 잇는 사슬은 여러 가지가 있습니다.

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

Abby에서 Alberto까지 가장 짧은 사슬은 두 개의 친구 관계(Abby–Zoey, Zoey–Alberto)를 사용하므로 두 사람의 분리 차수는 2이고, Alberto는 Abby의 친구의 친구입니다.

프로그램은 아래에 주어진 고정된 친구 관계에서 시작하여 명령들을 차례로 처리합니다. 시간이 지나면서 친구 관계가 새로 생기거나(때로는 처음 등장하는 사람과) 끊어질 수 있습니다. 어떤 사람의 친구 수, 친구의 친구 수, 그리고 임의의 두 사람 사이의 분리 차수를 답할 수 있어야 합니다.

초기 친구 관계

모든 사람은 괄호 안에 표시된 정수 id를 가집니다.

id	이름	id	이름	id	이름
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

네트워크는 정확히 다음의 상호 친구 관계로 시작하며, a-b 형태의 id 쌍으로 나타냅니다.

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

초기 친구 관계 네트워크

입력

각 명령은 한 줄에 하나씩 주어집니다. a와 b는 사람의 id입니다.

명령	의미
`i a b`	사람 `a`와 사람 `b`가 친구가 됩니다. 둘 중 한 명은 처음 등장하는 사람일 수 있습니다. 이미 친구라면 아무 변화도 없습니다.
`d a b`	사람 `a`와 사람 `b`의 친구 관계가 끊어집니다. 원래 친구가 아니었다면 아무 변화도 없습니다.
`n a`	사람 `a`가 현재 가진 친구의 수를 출력합니다.
`f a`	사람 `a`의 친구의 친구 수를 출력합니다.
`s a b`	사람 `a`와 사람 `b` 사이의 분리 차수를 출력합니다.
`q`	처리를 멈춥니다. 항상 마지막 명령입니다.

정의:

a의 친구의 친구 수는, a의 친구들 중 적어도 한 명과 친구인 서로 다른 사람의 수입니다. 단, a 자신과 a의 직접 친구는 세지 않습니다.
a와 b 사이의 분리 차수는 두 사람을 잇는 가장 짧은 사슬에 들어 있는 친구 관계의 수입니다. a와 b가 같은 사람이면 0입니다.

출력

모든 n, f, s 명령에 대해, 명령이 주어진 순서대로 요청한 값을 한 줄에 하나씩 출력합니다.

s 명령에서 두 사람을 잇는 친구 관계 사슬이 전혀 없으면 (따옴표 없이) 정확히 Not connected를 출력합니다.

제약 조건

모든 id는 1 이상 1,000,000 이하의 정수입니다.
명령은 최대 100,000개이며, 입력은 항상 하나의 q로 끝납니다.
모든 친구 관계는 상호적입니다.

예제1

예제 1

입력

예상 출력

2
3
4