시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB96585074.627%

## 문제

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.

## 출력 형식

정확한 출력 형식은 제출에서 언어를 Java로 설정하면 확인할 수 있다.

## 예제 입력 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


## 예제 출력 1

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