Under construction

Still being built. Things may change

Neighborhoods in Graphs

Interview

Time limit1sMemory limit256 MB

Summary
Count the distinct vertices at distance 1 or 2 from a query vertex in an undirected graph, excluding the vertex itself.
Level

Easy3 of 10

Topics
BFS, Graph
Solved
No attempts yet

Problem

Model co-conspirators as an undirected graph: each vertex is a super-villain, and each edge joins two villains who plotted together. For a given vertex vx, count how many other vertices lie within distance 1 or 2. Do not count vx itself.

Input

The first line contains T, the number of test cases. Each test case is one line with n, e, then 2e vertex names describing edges, and finally the query vertex vx. (n < 100, e < 1000)

Output

For each test case, print The number of supervillains in 2-hop neighborhood of vx is C, where C is the size of the 2-hop neighborhood.

Examples4

  1. Example 1

    Input
    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
    Expected output
    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. Example 2

    Input
    1
3 2 v1 v2 v2 v3 v1
    Expected output
    The number of supervillains in 2-hop neighborhood of v1 is 2

  3. Example 3

    Input
    1
4 3 v1 v2 v2 v3 v3 v4 v2
    Expected output
    The number of supervillains in 2-hop neighborhood of v2 is 3

  4. Example 4

    Input
    2
2 1 v1 v2 v1
3 0 v2
    Expected output
    The number of supervillains in 2-hop neighborhood of v1 is 1
The number of supervillains in 2-hop neighborhood of v2 is 0