Wedding

Interview

Time limit1sMemory limit128 MB

Summary

Given a friendship graph among n classmates, count everyone within distance 2 of classmate 1.

Level: Medium4 of 10
Topics: Graph, BFS, Implementation, Hash map
Solved: No attempts yet

Problem

Sanggeun wants to invite, from among his school classmates, his own friends and his friends' friends to his wedding. There are $N$ classmates in total, numbered from $1$ to $N$ , and Sanggeun's number is $1$ .

Given the list of all friendships among the classmates, write a program that determines how many classmates Sanggeun invites to the wedding. In other words, count the classmates who are friends with Sanggeun (number 1), or who are friends of Sanggeun's friends (friends of friends).

Input

The first line contains the number of classmates $n$ ( $2 \le n \le 500$ ). The second line contains the length of the friendship list $m$ ( $1 \le m \le 10000$ ). Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ( $1 \le a_i < b_i \le n$ ), meaning that classmate $a_i$ and classmate $b_i$ are friends.

Output

Print, on the first line, the number of classmates Sanggeun invites to the wedding.

Hint

Sanggeun invites the people who are directly his friends (distance 1) and the friends of those friends (distance 2). In the first example, classmates 2 and 3 are Sanggeun's friends; since 3 and 4 are friends, 4 is a friend of a friend. Classmates 5 and 6 are neither friends nor friends of friends, so Sanggeun invites 2, 3, and 4 — three people.

Examples2

Example 1
Input
```
6
5
1 2
1 3
3 4
2 3
4 5
```
Expected output
```
3
```
Example 2
Input
```
6
5
2 3
3 4
4 5
5 6
2 5
```
Expected output
```
0
```