## Editorial for SAC '22 Code Challenge 3 P4 - Finding Friends

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

##### Subtask 1

Maintain an adjacency list for all the friendships.

For a type query, start a BFS from and output the distance to (or `-1`

if it cannot be reached).

For a type query, loop through all the edges in and remove the one connecting it to ; likewise, loop through all the edges in and remove the one connecting it to .

**Time Complexity:**

##### Subtask 2

First, realize that if two friends are connected, they have a lowest common ancestor (LCA), so precompute the required values to query for the LCA between two nodes.

Then, reversing the operations (i.e., connecting friendships instead of destroying them by processing the last query first and first query last) allows us to maintain whether friends are connected by using a disjoint-set.

For a type query, if they are in the same component, query the distance between them by determining the LCA of and and then finding the distance from to the LCA and then the LCA to ; if they are not in the same component, output `-1`

.

For a type query, connect and with the union function of the disjoint-set.

**Time Complexity:**

Note that there are many solutions to this problem (including online solutions like link-cut tree).

## Comments