SAC has students with friendships between two friends (note: a friendship is bidirectional).
Recently, Mr. DeMello was tasked with monitoring friends and the friend-distance between them. The friend-distance is the minimum amount of friendships required to travel between two friends.
However, Mr. DeMello discovered that friendships could be destroyed, and all the current friendships would be destroyed eventually.
The school administrators ask Mr. DeMello queries of types:
1 u v: Output the friend-distance between friend and friend or
-1 if they are not connected by friends.
2 u v: Remove the friendship between friend and friend .
Since Mr. DeMello wants to get a raise, he has decided to ask you to kindly help him.
Can you do it?
For all subtasks:
Every friend can reach every other friend before any friendships are destroyed.
Every friendship will be deleted once in the queries.
Subtask 1 [30%]
Subtask 2 [70%]
The first line will contain and , the number of students and queries, respectively.
The next lines will contain and , a friendship between student and student .
The next lines will contain one of the above queries, a query for the friend-distance between student and student or a query to destroy a friendship between and .
For each type query, output the friend-distance or
-1 if they cannot reach each other through friends.
5 8 1 2 3 2 4 5 4 1 1 1 3 2 2 3 1 1 3 2 4 1 1 5 3 1 1 2 2 1 2 2 4 5
2 -1 -1 1