#K37352. Mutual Friends in a Social Network
Mutual Friends in a Social Network
Mutual Friends in a Social Network
You are given a social network with n users and m friendship relations. Each friendship is a bidirectional connection between two users. Your task is to determine the number of mutual friends between two specific users x and y.
A mutual friend of x and y is defined as a user who is directly connected (i.e. is a friend) of both x and y. Note that x and y should not be counted as their own mutual friend even if they are directly connected.
The input will be read from standard input (stdin) and the output should be printed to standard output (stdout). It is guaranteed that the provided friendship relations do not contain duplicates and represent undirected connections.
The mutual friends count is computed by finding the intersection of the friend lists of x and y.
Formally, if we denote the set of friends of user i as \(F(i)\), then the answer is \(|F(x) \cap F(y)|\).
inputFormat
The first line contains two integers n and m (\(1 \leq n \leq 10^5\), \(0 \leq m \leq 10^5\)) representing the number of users and the number of friendship relations respectively.
The next m lines each contain two integers u and v (\(1 \leq u, v \leq n\), \(u \neq v\)) indicating that user u and user v are friends.
The last line contains two integers x and y (\(1 \leq x, y \leq n\)) for which you need to calculate the number of mutual friends.
outputFormat
Output a single integer representing the number of mutual friends between users x and y.
## sample5 4
1 2
1 3
2 3
4 5
1 2
1