만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

그래프의 이웃

면접 대비

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

요약
무향 그래프에서 질의 정점을 제외하고 거리가 1 또는 2인 서로 다른 정점 수를 셉니다.
난이도

쉬움10점 중 3점

유형
BFS, 그래프
정답자
아직 제출이 없습니다

문제

무법자들의 공모 관계를 무방향 그래프로 나타낸다. 정점은 무법자, 간선은 한 번이라도 공모한 쌍이다. 주어진 무법자 vx에 대해 거리가 1 또는 2인 다른 정점의 개수를 구하라. vx 자신은 포함하지 않는다.

입력

첫 줄에 테스트 케이스 수 T가 주어진다. 각 테스트 케이스는 한 줄로 주어지며, 정점 수 n, 간선 수 e, 2e개의 정점 이름 쌍, 마지막에 조회할 정점 vx 순이다. (n < 100, e < 1000)

출력

각 테스트 케이스마다 The number of supervillains in 2-hop neighborhood of vx is C 형식으로 출력한다. C는 2-hop 이웃의 크기이다.

예제4

  1. 예제 1

    입력
    4 
9 11 v1 v3 v2 v3 v3 v4 v3 v5 v4 v7 v5 v6 v5 v9 v6 v7 v6 v9 v7 v8 v8 v9 v1
9 11 v1 v3 v2 v3 v3 v4 v3 v5 v4 v7 v5 v6 v5 v9 v6 v7 v6 v9 v7 v8 v8 v9 v5 
5 4 v1 v2 v2 v3 v3 v4 v4 v5 v1 
5 0 v1
    예상 출력
    The number of supervillains in 2-hop neighborhood of v1 is 4
The number of supervillains in 2-hop neighborhood of v5 is 8
The number of supervillains in 2-hop neighborhood of v1 is 2
The number of supervillains in 2-hop neighborhood of v1 is 0

  2. 예제 2

    입력
    1
3 2 v1 v2 v2 v3 v1
    예상 출력
    The number of supervillains in 2-hop neighborhood of v1 is 2

  3. 예제 3

    입력
    1
4 3 v1 v2 v2 v3 v3 v4 v2
    예상 출력
    The number of supervillains in 2-hop neighborhood of v2 is 3

  4. 예제 4

    입력
    2
2 1 v1 v2 v1
3 0 v2
    예상 출력
    The number of supervillains in 2-hop neighborhood of v1 is 1
The number of supervillains in 2-hop neighborhood of v2 is 0