Description

In this assignment, you will model a simple social network using a Graph. The network consists of users, represented as nodes, and follow relationships, represented as directed edges. You will implement a system that processes a series of commands to build and then traverse 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. For U users, you can think of this as an array of lists, where the i-th list contains all the users that user i follows.

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

1. add u v: Add a follow relationship, where user u follows user v. This is a directed edge from u to v.
2. dfs u: Perform a Depth-First Search (DFS) starting from user u.
3. bfs u: Perform a Breadth-First Search (BFS) starting from user u.

For the traversal commands (dfs and bfs), you must follow two rules to ensure your output is correct:

• You should only visit each node once. If a node has already been visited (in the current traversal), do not visit it again or add it to your stack/queue.
• When exploring the neighbors of a node (the users they follow), you must process them in ascending order of their user ID.

Format

Input

• The first line contains two integers, U and N, where U ($1 \leq U \leq 10,000$) is the number of users and N ($1 \leq N \leq 20,000$) is the total 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$).
  • dfs u: The string dfs followed by a single space and an integer u ($0 \leq u < U$).
  • bfs u: The string bfs followed by a single space and an integer u ($0 \leq u < U$).
• It is guaranteed that for any user u, all add u v operations will be given in increasing order of v.
• It is guaranteed that the total number of dfs and bfs operations will not exceed 50.

Output

• For each dfs operation, print the sequence of nodes visited (in the order they were visited) on a new line, with each node ID separated by a single space.
• For each bfs operation, print the sequence of nodes visited (in the order they were visited) on a new line, with each node ID separated by a single space.
• 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
dfs 0
bfs 1
dfs 4

0 1 2 3
1 2 3
4 5

Explanation:

1. After the add operations, the follow relationships (directed edges) are: 0->1, 0->2, 1->2, 1->3, 4->5.
2. The (sorted) adjacency lists are:
   • 0: [1, 2]
   • 1: [2, 3]
   • 2: []
   • 3: []
   • 4: [5]
   • 5: []
3. dfs 0:
   • Start at 0. Print 0.
   • Neighbors of 0 are [1, 2]. Visit smallest: 1. Print 1.
   • Neighbors of 1 are [2, 3]. Visit smallest unvisited: 2. Print 2.
   • Neighbors of 2 are []. Backtrack to 1.
   • Neighbors of 1 are [2, 3]. 2 is visited. Visit smallest unvisited: 3. Print 3.
   • Neighbors of 3 are []. Backtrack.
   • Traversal ends.
   • Output: 0 1 2 3
4. bfs 1:
   • Queue: [1]. Mark 1 visited.
   • Dequeue 1. Print 1. Neighbors are [2, 3]. Enqueue 2, 3 in order. Mark 2, 3 visited.
   • Queue: [2, 3].
   • Dequeue 2. Print 2. Neighbors are [].
   • Queue: [3].
   • Dequeue 3. Print 3. Neighbors are [].
   • Queue: []. Traversal ends.
   • Output: 1 2 3
5. dfs 4:
   • Start at 4. Print 4.
   • Neighbors of 4 are [5]. Visit 5. Print 5.
   • Neighbors of 5 are []. Backtrack.
   • Output: 4 5

10 7
add 0 1
add 1 2
add 2 3
add 1 4
dfs 1
bfs 1
dfs 5

1 2 3 4
1 2 4 3
5

Explanation:

1. After the add operations, the follow relationships are: 0->1, 1->2, 2->3, 1->4.
2. The (sorted) adjacency lists are:
   • 0: [1]
   • 1: [2, 4] (Note: add 1 2 and add 1 4 are guaranteed to be in this order)
   • 2: [3]
   • 3: []
   • 4: []
   • Users 5-9 have no followers and follow no one.
3. dfs 1:
   • Start at 1. Print 1.
   • Neighbors [2, 4]. Visit 2. Print 2.
   • Neighbors [3]. Visit 3. Print 3. (3 has no neighbors). Backtrack.
   • Neighbors [2, 4]. 2 is visited. Visit 4. Print 4. (4 has no neighbors). Backtrack.
   • Output: 1 2 3 4
4. bfs 1:
   • Queue: [1]. Mark 1 visited.
   • Dequeue 1. Print 1. Neighbors are [2, 4]. Enqueue 2, 4. Mark 2, 4 visited.
   • Queue: [2, 4].
   • Dequeue 2. Print 2. Neighbors are [3]. Enqueue 3. Mark 3 visited.
   • Queue: [4, 3].
   • Dequeue 4. Print 4. Neighbors are [].
   • Queue: [3].
   • Dequeue 3. Print 3. Neighbors are [].
   • Output: 1 2 4 3
5. dfs 5:
   • Start at 5. Print 5. User 5 has no neighbors. Traversal ends.
   • Output: 5

Hint

• Important: You are guaranteed that for any user u, all add u v commands will be given in increasing order of v. This means you can just use adj[u].append(v) to add an edge, and each adjacency list will automatically be sorted.

• Remember that the graph is directed. When you add u v, you only need to update the adjacency list for u.

• For DFS, you can use recursion or an explicit stack.

• For BFS, you will need a queue.

• Test case 1 to 5 only contain add and dfs operations.

• Test case 6 to 10 only contain add and bfs operations.

• Test case 11 to 15 contain all three types of operations.

Limitation

1s, 256MiB for each test case.