The Amestris government has been alerted of cities, numbered to . However, they are going to be slowly reopening roads, at a steady rate of road per day, for days to . knows their plan, and will only move between two cities if he knows that they are in the same strangely connected component. He will ask queries in the form "", asking the first day on which and will be strangely connected, or if it will never be strangely connected.’s plan, and has decided to shut down all bidirectional roads between its
Note: We define a strangely connected component as a connected component that will not be disconnected by removing any 1 edge.
Next lines: integers and , representing that cities and are connected on the -th day.
Next lines: integers and , representing a query.
For full points,
For 5/25 points,
4 5 3 3 3 1 3 3 0 3 2 2 3 0 2 3 3 0 3
-1 0 -1