I am looking for the best way to handle a database of many-to-many relationships in PHP and MySQL.

Right now I have 2 tables:

Users (id, user_name, first_name, last_name)
Connections (id_1, id_2)

In the User table id is auto incremented on add and user_name is unique, but can be changed. Unfortunately, I don't have control over the user_name and its ability to be changed, but I must account for it.

The Connections table is obviously, user1 and user2's id.

The connection table needs to account for these possible relations:

user1 --> user2 (user 1 friends with user 2 but not user2 friends with user1) 
user2 --> user1 (user 2 friends with user 1 but not user1 friends with user2) 
user1 <--> user2 (user 1 and user 2 mutually friends) 
user1 <-!-> user2 (user 1 and user 2 not friends) 

That part is not the problem, The problem I am having with is keeping these relations unique when and if they change in batches.

Possible solution 1: delete all of user 1's relations and readd them with the updated list. I think this might be too slow for my needs.

Solution 2? Anyone else encounter this problem? How should I best handle this?

update: distinguishing relationships:

i handle relationships like this:

user1, user2
user1, user3
user2, user1

in that example the following is true:
user1 follows user2 and user3
user2 only follows user1 but doesn't follow user3
user3 doesn't follow either user1 or user2