Người ta khởi tạo một đồ thị có hướng gồm 109 đỉnh các đỉnh được đánh số từ 1 tới 109, ban đầu đồ thị không có cung nào. Người ta thêm lần lượt các cung vào đồ thị bởi câu lệnh dạng add(u, v), nghĩa là thêm một cung nối từ đỉnh u tới đỉnh v trên đồ thị.
Cho trước 2 đỉnh s và t, hãy cho biết số thứ tự của lệnh add đầu tiên mà sau thời điểm thực hiện lệnh add đó đỉnh s có thể đi tới được đỉnh t theo một số cung của đồ thị.
Input
Output
5 1 5
1 2
3 5
3 1
2 3
2 4
out:
4