Description

In this assignment, you will model a simple social network using a Graph. The network consists of users, represented as nodes, and friendships, represented as undirected edges. You will implement a system that processes a series of commands to build and query this social network.

The social network will be represented using an Adjacency List. An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph. For U users, you can think of this as an array of lists, where the i-th list contains all the users who are friends with user i.

You will process a sequence of commands, each representing one of the following operations:

1. add u v: Add a friendship between user u and user v. Since friendships are mutual, this is an undirected edge.
2. degree u: Count the total number of friends user u has.
3. isfriend u v: Check if user u and user v are friends.
4. count_greater x: Count how many users in the network have strictly more than x friends.

Format

Input

• The first line contains two integers, U and N, where U ($1 \leq U \leq 10^5$) is the number of users and N ($1 \leq N \leq 2 \cdot 10^5$) is the number of operations. Users are identified by integers from 0 to U-1.
• The next N lines each contain an operation. The operation will be one of the following:
  • add u v: The string add followed by two space-separated integers u and v ($0 \leq u, v < U, u \neq v$).
  • degree u: The string degree followed by a single space and an integer u ($0 \leq u < U$).
  • isfriend u v: The string isfriend followed by two space-separated integers u and v ($0 \leq u, v < U$).
  • count_greater x: The string count_greater followed by a single space and an integer x ($0 \leq x < U$).

Output

• For each degree operation, print the integer result on a new line.
• For each isfriend operation, print yes or no on a new line.
• For each count_greater operation, print the integer count on a new line.
• The add operation should not produce any output.

Samples

6 8
add 0 1
add 0 2
add 1 2
add 1 3
add 4 5
isfriend 0 1
degree 1
count_greater 1

yes
3
3

Explanation:

1. After the add operations, the friendships are: (0,1), (0,2), (1,2), (1,3), (4,5).
2. The number of friends (degree) for each user is:
   • degree(0) = 2
   • degree(1) = 3
   • degree(2) = 2
   • degree(3) = 1
   • degree(4) = 1
   • degree(5) = 1
3. isfriend 0 1: Users 0 and 1 are directly connected. Output: yes.
4. degree 1: User 1 has 3 friends (0, 2, and 3). Output: 3.
5. count_greater 1: We need to count users with more than 1 friend. These are user 0 (2 friends), user 1 (3 friends), and user 2 (2 friends). The total count is 3. Output: 3.

10 10
add 0 1
add 1 2
add 2 3
add 1 4
degree 1
degree 5
isfriend 1 3
isfriend 0 2
count_greater 0
count_greater 2

4
0
no
no
5
1

Explanation:

1. After the add operations, the friendships are: (0,1), (1,2), (2,3), (1,4).
2. The degrees are: deg(0)=1, deg(1)=4, deg(2)=2, deg(3)=1, deg(4)=1. All other users have 0 friends.
3. degree 1: User 1 is friends with 0, 2, 3, and 4. Output: 4.
4. degree 5: User 5 has no friends. Output: 0.
5. isfriend 1 3: User 1 and 3 are not directly connected. Output: no.
6. isfriend 0 2: User 0 and 2 are not directly connected. Output: no.
7. count_greater 0: Users 0, 1, 2, 3, 4 all have more than 0 friends. Count is 5. Output: 5.
8. count_greater 2: Only user 1 (degree 4) has a degree strictly greater than 2. Count is 1. Output: 1.

Hint

• An adjacency list is a good way to store the graph. You can use a vector of vectors, or a map where keys are user IDs and values are lists of their friends.
• Remember that the graph is undirected. When you add u v, you must update the adjacency lists for both u and v.
• For the degree operation, the size of a user's adjacency list is their degree.
• For the isfriend operation, you can check if v is in u's adjacency list. A simple loop through the list is sufficient.
• For the count_greater operation, you will need to iterate through all U users, find the degree of each, and count how many have a degree greater than x.

Limitation

1s, 256MiB for each test case.