|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||256 MB||5||5||5||100.000%|
Gru and Lucy put together a graph of super-villains to see if they can see any interesting connections, in order to find who stole the Arctic Circle Laboratory. In this graph, there is a node (vertex) for every super-villain, and there is an edge (connection) between two nodes if they have ever concocted a sinister plot together. The figure below shows an example of such a graph over 10 villains (to simplify things for you, we will use made-up simple names for the super-villains, of the form v1, v2, ..., and so on).
Given such a graph and a super-villain, your goal is to count to the number of super-villains in that super-villain’s 2-hop neighborhood in the graph, i.e., all the nodes that are within a distance of 2 from the given node. (This is also called “friends of friends query” in a social graph setting.) For example, for v1, this includes: v3, v2, v5, and v4 (so the answer would be 4), whereas for v5, the 2-hop neighborhood includes: v1, v2, v3, v4, v6, v7, v8, v9, i.e., all the nodes in the graph (so the answer would be 8). Note that, we don’t count v5 to be in its own 2-hop neighborhood.
The first line in the test data file contains the number of test cases (< 100). After that each line contains a test case. The first two numbers in each test case represent the number of supervillains in the graph, n (n < 100), and the number of edges in the graph, e (e < 1000). After that, the next 2e Strings describe the edges. The last String on each line contains the id of a supervillain, vx.
For each test case, you are to output the number of nodes in the 2-hop neighborhood of vx. The exact format is shown below in the examples.
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